백준 1563 개근상

백준 1563 개근상

www.acmicpc.net/problem/1563

1563번: 개근상

전형적인 dp문제이다. 이전의 정보를 이용해서 풀어야하는데 문제를 맞고나서 다른 사람들의 풀이를 보니 대부분 다르게 풀어서 내가 푼 방법을 공유하려고한다.

 

우선 3차원 배열을 이용해 

 

dp[일][지각의 수][연속된 결석의 수]로 표현해주었다. 

 

해당 일에 지각의 수와 연속된 결석의 수의 개근상이 가능한 사람의 수가 된다. 

 

그럼 배열로 나타낼 수 있는 경우의 수는 얼마나 될까?

 

dp[요일][0][0] = dp[요일 - 1][0][0] + dp[요일-1][0][1] + dp[요일 - 1][0][2];

결석 다음으로 0이 오게되면 연속되지 않기 때문에 [0][0]과 동일하다. 

 

dp[요일][0][1] = dp[요일-1][0][0]

01이 될수있는 경우의 수는 00에서 결석을 하는 것이다. 

 

dp[요일][1][0] = dp[요일-1][0][0] +dp[요일-1][1][0] +  dp[요일-1][0][1] +  dp[요일-1][0][2] + dp[요일-1][1][2] + dp[요일-1][1][1];

 

dp[요일][1][1] = dp[요일-1][1][0];

 

dp[요일][0][2] = dp[요일-1][0][1];

 

dp[요일][1][2] = dp[요일-1][1][1];

 

이런 점화식이 나올 수 있는 이유는 무엇일까???

 

출석출석[0][0] + 결석 = 출석출석결석 [0][1]

결석출석[0][0] + 결석 = 결석출석결석 [0][1]

 

즉 위의 경우와 같이 출석출석, 결석 출석은 결석과 출석을 한번도 한적이 없는 것과 같기 때문에 결석을 더해주면 [0][1]이 된다. 

 

출석출석[0][0] + 지각 = 출석출석지각[1][0]

결석출석[0][0] + 지각 = 결석출헉지각[1][0]

지각결석[1][1] + 등교 = 지각결석등교[1][0]

 

즉 위와 같이 마지막에 어떤 값이 오느냐에 따라 다음의 값은 결정하게 되는 것이기 때문에 위와 같은 점화식이 나오게 된다. 

 

위와 같이 점화식이 구성된다. 해당 요일에 될 수 있는 경우의 수를 dp[요일-1]로 더해줌으로써 개수를 구할 수 있었다.

#include <cstdio>
#define ll long long

ll dp[1002][5][5];

int main(){
	int N;
	scanf("%d", &N);

	dp[1][0][0] = 1;
	dp[1][0][1] = 1;
	dp[1][1][0] = 1;

	for(int i = 2; i <= N; i++){
		for(int y = 0; y < 2; y++){
			for(int x  = 0; x < 3; x++){
				if(y == 0 && x == 0){
					dp[i][y][x] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % 1000000;
				}else if(y == 1 && x == 0){
					dp[i][y][x] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2] + dp[i-1][0][2]) % 1000000;
				}else if(y ==0 && x == 1){
					dp[i][y][x] = (dp[i-1][0][0]) % 1000000;
				}else if(y == 1 && x == 1){
					dp[i][y][x] = (dp[i-1][1][0]) % 1000000;
				}else if(y == 0 && x == 2){
					dp[i][y][x] = (dp[i-1][0][1]) % 1000000;
				}else if(y == 1 && x == 2){
					dp[i][y][x] = (dp[i-1][1][1]) % 1000000;
				}
			}
		}
	}
	ll result = 0;
	for(int y = 0; y < 2; y++){
		for(int x  = 0; x < 3; x++){
			result += dp[N][y][x];
			result%=1000000;
		}
		result%=1000000;
	}

	printf("%lld", result);
}