백준 1563번 : 개근상

  초기 조건을 좀 많이 적었다..ㅋㅋㅋ 더 깔끔하게 하는 방법이 있을 수도 있지만.. 그래도 뭐 풀었으면 된 거지

---

  나는 지각은 마지막에 한 번 고려했다. 그래서 일단 dp를 다음과 같이 정의했다.

 

dp [n][k] : n일 동안 k번 결석하고 개근상을 받을 수 있는 경우의 수

 

  이런 형태의 문제는 흔하다. 연속되는 계단을 오르지 않거나 하는 문제 등 여러 곳에서 볼 수 있다. 이 경우 결석을 연속 세 번은 할 수 없다.

 

1. n일 째에 출석하는 경우 = dp [n-1][k]

이 경우 n-1일 동안 k번의 결석을 해야 하는데 어차피 마지막 날에 출석할 것이기 때문에 아무런 제약이 없다.

 

2. n일 째에 결석하는 경우

n일째에 결석하는 경우 연속으로 3번 결석할 수 있기 때문에 좀 더 세부적으로 경우를 나눠야 한다.

  2.1. n-1일째에 출석하고 n일째에 결석하는 경우 = dp [n-2][k-1]

  이 경우 n-1일째에 출석을 했으므로 n-2일 동안 k-1번의 결석을 아무런 제약 없이 하면 된다.

  2.2. n-1일째에 결석하고 n일째에 결석하는 경우 = dp [n-3][k-2]

  이 경우 n-2일째에도 결석을 하면 연속 세 번 결석이므로 반드시 n-2일째에는 출석을 해야 한다. 따라서 n-3일 동안 k-2번의 결석을 아무런 제약 없이 하면 된다.

 

dp [n][k] = dp [n-1][k] + dp [n-2][k-1] + dp [n-3][k-2]

 

  이렇게 dp를 계산하고 나면 n일 동안 k번의 결석을 하면서 개근상을 받을 수 있는 경우의 수가 구해진다. 이제 여기서 지각을 고려해주면 되는데 지각은 아예 안 하거나 딱 한 번만 해야 한다.

 

1. 지각을 아예 안 하는 경우 = dp [n][k]

2. 지각을 한 번만 하는 경우 = (n-k) * dp [n][k]

 

  지각을 한 번 할 경우에는 기존의 출석이었던 하나를 지각으로 교체할 수 있다. 그 경우의 수는 출석한 횟수(n-k)와 같기 때문에 (n-k)를 곱해주면 된다.

 

#include <iostream>

using namespace std;

int n;
int dp[1002][1002];
int DIV = 1000000;

int main()
{
    cin >> n;
    
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[2][0] = 1;
    dp[2][1] = 2;
    dp[2][2] = 1;
    dp[3][0] = 1;
    dp[3][1] = 3;
    dp[3][2] = 3;
    
    for(int i = 4; i <= n; i++)
    {
        for(int j = 0; j*1.5 <= i+1; j++)
        {
            if(i-1 >= 0 && j >= 0)   dp[i][j] = (dp[i][j] + dp[i-1][j]) % DIV;
            if(i-2 >= 0 && j-1 >= 0) dp[i][j] = (dp[i][j] + dp[i-2][j-1]) % DIV;
            if(i-3 >= 0 && j-2 >= 0) dp[i][j] = (dp[i][j] + dp[i-3][j-2]) % DIV;
        }
    }
    
    int ans = 0;
    
    for(int i = 0; i <= n; i++)
    {
        ans = (ans + (dp[n][i] * (n-i+1)) % DIV) % DIV;
    }
    
    cout << ans;

    return 0;
}