취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1563번 문제인 개근상이다.
문제는 아래 링크를 확인하자.

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

상태를 6가지로 분류해서 점화식을 세우고, dp를 해보자.

0) 지각횟수 0회, 현재 연속 결석 0일

1) 지각횟수 0회, 현재 연속 결석 1일

2) 지각횟수 0회, 현재 연속 결석 2일

3) 지각횟수 1회, 현재 연속 결석 0일

4) 지각횟수 1회, 현재 연속 결석 1일

5) 지각횟수 1회, 현재 연속 결석 2일

아래는 제출한 소스코드이다.

#define MOD 1000000
#include <iostream>
using namespace std;

int dp[1001][6]; // (이번 것으로) 0: O로 끝남, 1: A 1회 끝남, 2: A 2회 끝남

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp[0][0] = 1;
	int N; cin >> N;
	for (int k = 1; k <= N; k++) {
		dp[k][0] = (dp[k - 1][0] + dp[k - 1][1] + dp[k - 1][2]) % MOD;
		dp[k][1] = dp[k - 1][0];
		dp[k][2] = dp[k - 1][1];
		dp[k][3] = (dp[k - 1][0] + dp[k - 1][1] + dp[k - 1][2] + dp[k - 1][3] + dp[k - 1][4] + dp[k - 1][5]) % MOD;
		dp[k][4] = dp[k - 1][3];
		dp[k][5] = dp[k - 1][4];
	}

	cout << (dp[N][0] + dp[N][1] + dp[N][2] + dp[N][3] + dp[N][4] + dp[N][5]) % MOD << '\n';
}