[BAE/<JOON> 문제풀이] 1563. 개근상

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

1563번: 개근상

서론

내가 복잡하게 푼건진 모르겠는데 DP 축이 많아서 점화식 세울 때 헷갈린다.

---

아이디어

솔직히 아이디어랄건 없고 그냥 문제에서 주어진 점화식을 구현하면 된다.

지금 연속 결석 횟수 몇번인지, 지각 여부 ( 지각 기회는 딱 1번 뿐임 ), 현재 몇 번째 출결인지 3가지 요소로 계산 가능

---

풀이

진짜 순수 DP 라서 점화식밖에 쓸게 없다. :D

DP[i][j][k] = i 번째날에 j번 지각하고 현재 k번 연속 지각한 경우 횟수

• 오늘 지각한 경우
  오늘 지각했으므로 연속 결석 횟수는 무조건 0으로 초기화 된다.
  경우 수는 어제까지 지각 안한 경우 수의 총합이다.
  DP[i][1][0] = sum(DP[i - 1][0][0], DP[i - 1][0][1], DP[i - 1][0][2])
• 오늘 결석한 경우 ( 결석했으므로 k=0은 불가능하다. k = 1, 2 )
  그냥 이전 날 결석 카운트가 오늘보다 1 적은 값 그대로 가져오면 된다. 자명하다.
  DP[i][j][k] = DP[i - 1][j][k - 1]
• 오늘 정상 출석한 경우
  어제의 모든 값들을 오늘 결석 카운트 0값에 더하면 된다.
  DP[i][j][0] = sum(DP[i - 1][j][k])

답은 마지막 날 경우 수의 합이다. ( sum(DP[n][j][k] ) 

---

코드

근데 솔직히 풀면서 헷갈렸다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int mod = 1000000;
int dp[1001][2][3]; // len, late, absent
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n; 
	dp[1][0][0] = 1;
	dp[1][1][0] = 1;
	dp[1][0][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 3; j++) { // 처음 지각한 경우			
			dp[i][1][0] += dp[i - 1][0][j];
			dp[i][1][0] %= mod;
		}
		for (int k = 0; k < 2; k++) {		
			for (int l = 0; l < 3; l++) {
				dp[i][k][0] += dp[i - 1][k][l];
				dp[i][k][0] %= mod;
			}
			dp[i][k][1] += dp[i - 1][k][0];
			dp[i][k][1] %= mod;
			dp[i][k][2] += dp[i - 1][k][1];
			dp[i][k][2] %= mod;
		}
	}
	int sum = 0;
	
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 3; j++) {
			//cout << dp[n][i][j] << " ";
			sum += dp[n][i][j];
			sum %= mod;
		}
		//cout << "\n";
	}
	cout << sum;
	return 0;
}