boj 1563 개근상

https://www.acmicpc.net/problem/1563

1563번: 개근상

점화식 구하는게 좀 복잡할 수도 있는 dp문제입니다.

문제를 풀고나서 다른분들의 풀이를 보니 3차원배열을 사용하셨던데 저는 2차원 dp배열로 해결하였습니다.

 

우선 이 문제는 지각을 두 번 이상 하거나, 결석을 세 번 연속으로 하는 경우를 제외한 모든 경우의 수를 구해야합니다.

 

손으로 직접 그려본 후에 점화식을 찾았습니다.

dp[N][start] : 학기 첫날(start)이 출석 / 지각 / 결석일 때 N번째 날의 경우의 수

		[0]	[1]	[2]	sum
N = 1	 1	1	1	3

N = 2	 3	2	3	8

N = 3	 8	4	7	19

N = 4	 19	7	17	43

N = 5	 43	13	38	94

N = 6	 94	24	82	200

 

dp[N][0] : 첫날이 출석인 경우의 수

 -> dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]

dp[N][1] : 첫날이 지각인 경우의 수

 -> dp[N - 1][1] + dp[N - 2][1] + dp[N - 3][1]

dp[N][2] : 첫날이 결석인 경우의 수

 -> dp[N - 1][0] + dp[N - 1][1] + dp[N - 2][0] + dp[N - 2][1]

 

출력은 dp[N][0 ~ 2]를 더해 1000000으로 mod연산한 값을 출력해주시면 됩니다.

#include <iostream>
#define MOD 1000000
using namespace std;
 
int dp[1001][3];
int N;
 
void init() {
    dp[0][1] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;
    dp[2][0] = 3;
    dp[2][1] = 2;
    dp[2][2] = 3;
    for (int i = 3; i <= 1000; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
        dp[i][1] = (dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]) % MOD;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 2][0] + dp[i - 2][1]) % MOD;
    }
}
 
void input() {
    cin >> N;
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) % MOD << '\n';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
 
    return 0;
}