c언어 15990번 1, 2, 3 더하기 5 (백준)

#include <stdio.h>
#define M 1000000009

int main(void) {
	int t, i, n, ans, dp[100001][3] = {};
	scanf("%d", &t); //testcase 입력
	
    //1부터 3까지 만드는 것은 기본적으로 넣습니다.
	dp[1][0] = 1;
	dp[2][1] = 1;
	dp[3][0] = 1;
	dp[3][1] = 1;
	dp[3][2] = 1;
	
    //4이상 부터는 dynamic programming으로 얻어낼 수 있습니다.
	for(i=4; i<=100000; i++) { //100000까지 얻어냅니다. M으로 나누어야 overflow가 일어나지 않습니다.
		dp[i][0] = (dp[i-1][1] + dp[i-1][2])%M;
		dp[i][1] = (dp[i-2][0] + dp[i-2][2])%M;
		dp[i][2] = (dp[i-3][0] + dp[i-3][1])%M;
	}
	
	while(t--) { 
		scanf("%d", &n); //n을 입력받기
		ans = (((dp[n][0] + dp[n][1]) % M) + dp[n][2]) %M;
		printf("%d\n", ans); 
	}
}

 

풀이 : dynamic programming

 

1부터 3까지는

 

1 : 1

2 : 2

3 : 1+2, 2+1 로 볼 수 있습니다.

 

4는 맨 앞을 기준으로 분류해보면

 

1 : 1+ 2 + 1, 1 + 3

2 : 없음

3 : 3 + 1

 

즉 시작이 1, 2, 3으로 나눠서 dp을 이용 할 수 있습니다.

나눠야 하는 이유는 1 + 1 + 2 이런식으로 같은 숫자를 연속해서 더할 수 없기 때문입니다.

 

고로 1이 앞인 것을 구할 때는 그다음 것이 2이거나 3인것을'

2가 앞인 것을 구할 때는 그다음 것이 1이거나 3인것을

3이 앞인 것은 그 다음것이 1이거나 2인것을 더해야 합니다.

 

 

dp[4][], dp[5][]의 과정을 n = 100000 까지 반복한 다음

 

n을 입력 받을 때 마다 이에 대한 dp[n]을 불러오면 됩니다

 

 

 

 

 

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

15990번: 1, 2, 3 더하기 5