백준 15990. 1,2,3 더하기 5

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

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

 

좀 더 풀어보기로 한 dp 문제.

 

중요한 부분은 같은 수를 연속으로 쓸수 없다는 것.

d[100010][3] 배열을 만든다. 

각 행은 숫자를 뜻하고, 열은 순서대로 1로 끝나는 경우, 2로 끝나는 경우, 3으로 끝나는 경우이다. 

 

d[1] = {1, 0, 0} // 1

d[2] = {0, 1, 0} // 2 

d[3] = {1,1,1} // 1+2, 2+1, 3

...

 

1로 끝나는 경우 : i-1 번째 숫자 + 1

2로 끝나는 경우 : i-2 번째 숫자 + 2

3로 끝나는 경우 : i-3 번째 숫자 + 3

 

그런데 같은 수를 연속해서 쓸수 없으므로 i-j번째 숫자라면 j로 끝나는 방법은 제외해야한다.

 

즉 점화식은 

d[i][0] = (d[i-1][1] + d[i-1][2]) % MOD;
d[i][1] = (d[i-2][0] + d[i-2][2]) % MOD;
d[i][2] = (d[i-3][0] + d[i-3][1]) % MOD;