스터디 23/01/21 1563 : 개근상

1563번: 개근상 (acmicpc.net)

1563번: 개근상

풀이
DP로 풀이한다.
DP[n][l][a] = n번째 날까지 지각을 l번하고 결석을 a번한 경우의 수
지각을 2번하거나 결석을 3번한 경우 0을 리턴하고 n이 끝까지 가면 1을 리턴하여 모든 경우를 구한다.

 

시간복잡도 : O(n*2*3)

#include<bits/stdc++.h>
#include<time.h>


#define MAX 5000001
#define INF 2000000000
#define MOD 1000000
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

ll dp[1001][2][3];
int n;
int func(int d,int l,int a) {
    if (l >= 2 || a >= 3)
        return 0;
    else if (n == d)
        return 1;

    ll& res = dp[d][l][a];
    if (res != -1) return res;

    res = 0;
    res += func(d + 1, l + 1, 0);
    res %= MOD;
    res += func(d + 1, l, 0);
    res %= MOD;
    res += func(d + 1, l, a + 1);
    res %= MOD;

    return res;
}
int main() {
    init();
    memset(dp, -1, sizeof(dp));
    cin >> n;
    cout<< func(0, 0, 0);
}