[BOJ] 1563번 개근상 (C++)

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

1563번: 개근상

 

#include <iostream>
#include <vector>
using namespace std;

const int divval = 1000000;
int dp[1001][2][3];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	dp[1][0][0] = dp[1][1][0] = dp[1][0][1] = 1;
	
	for(int i = 2; i <= n; i++){
		dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % divval;
		dp[i][0][1] = (dp[i - 1][0][0]) % divval;
		dp[i][0][2] = (dp[i - 1][0][1]) % divval;
		dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % divval;
		dp[i][1][1] = (dp[i - 1][1][0]) % divval;
		dp[i][1][2] = (dp[i - 1][1][1]) % divval;
	}
	
	int ans = (dp[n][0][0] + dp[n][0][1] + dp[n][0][2] + dp[n][1][0] + dp[n][1][1] + dp[n][1][2]) % divval;
	
	cout << ans << endl;
	return 0;
}

 

dp[날짜][지각 횟수][연속으로 결석한 횟수]로 정의했다.

 

 

n번째 날에 개근상을 받을 수 있는 사람들의 조건은 다음과 같다.

1) 0번 지각 0번 연속 결석 -> dp[n][0][0]

2) 0번 지각 1번 연속 결석 -> dp[n][0][1]

3) 0번 지각 2번 연속 결석 -> dp[n][0][2]

4) 1번 지각 0번 연속 결석 -> dp[n][1][0]

5) 1번 지각 1번 연속 결석 -> dp[n][1][1]

6) 1번 지각 2번 연속 결석 -> dp[n][1][2]

 

 

n번째 날의 0번 지각 0번 연속 결석은 무조건 출석을 해야 도달할 수 있다.

1번, 2번 연속 결석한 사람도 출석을 하면 0번으로 초기화되므로

dp[n][0][0] = dp[n - 1][0][0] + dp[n - 1][0][1] + dp[n - 1][0][2]

 

0번 지각 1번 연속 결석은 무조건 결석을 해야한다. dp[n][0][1] = dp[n - 1][0][0]

0번 지각 2번 연속 결석도 마찬가지로 결석을 해야한다. dp[n][0][2] = dp[n - 1][0][1]

 

1번 지각 0번 결석은 지각해서 도달할 수도 있고, 출석해서 도달할 수도 있다.

dp[i][1][0] = dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]

 

dp[n][1][1], dp[n][1][2]는 dp[n][0][1], dp[n][0][2]와 비슷한 구조다.