백준 15990 (Python 파이썬)

 

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

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

 

이번 문제 역시 DP문제이다. 이번 문제 관련하여 이거보다 조금 더 쉬운 1,2,3 더하기가 있었는데, 그 친구는 점화식만 간단하게 구하면 되는 문제여서 어려운 점이 없었다. 하지만, 이번 친구는 DP테이블을 구상하는 것부터 다른 문제들과 달랐기 때문에 어려움이 좀 있었다. 1시간 정도 고민하다가 해결할 수 없다 판단하여 구선생님의 도움을 조금 받았다. 이 문제는 이전 값의 결과가 다음 값에 영향을 미친다. 1을 만들어주려면 1 하나, 2를 만들어 주려면 1+1은 연속되는 것이기 때문에 안되고 2 하나만 된다. 3은 1+2, 2+1, 3 이렇게 연속되지 않는 값으로 3개를 만들어 줄 수 있기 때문에 3이 된다. 위에서 보면 알겠지만, 이전 값들의 영향을 상당히 많이 받는다. 4를 만들어주는 것을 표로 보자.

0	1	2	3	4
0	1	0	1
0	0	1	1
0	0	0	1

표는 위와 같이 구성되어 있다. 행은 인덱스를 나타내며, 열은 인덱스를 만들어주는데 필요한 연속되지 않은 수를 의미한다. 4를 구해보자. 일단 3에서 1을 더하면 4가 되기 때문에 3을 만들어 줄 수 있었던 것에 +1을 해주면 된다. 하지만, 3을 만들 때 마지막에 1이 붙었던 첫 번째 열은 들어올 수 없기 때문에 2번째와 3번째 열만 더해주면 된다. 

0	1	2	3	4
0	1	0	1	2
0	0	1	1
0	0	0	1

1을 적용하면 위와 같이 된다. 이제 여기서 점화식을 만들어 줄 수 있다. 위 테이블을 dp테이블이라고 정의하자. 1,2,3 중 1의 경우의 수는

dp [j] = dp [j-1][1] + dp [j-1][2]가 된다. 하나만 만들어 주면 나머지 2, 3도 똑같이 해주면 된다.

dp [j] = dp [j-2][0] + dp [j-2][2]

dp [j] = dp [j-3][0] + dp [j-3][1]

위와 같이 만들어 주면 dp 테이블이 세팅된다. 이후에는 원하는 값의 인덱스를 다 더한 것을 출력해주면 된다.

import sys
n = int(sys.stdin.readline())
array = []
for i in range(n):
    a = int(sys.stdin.readline())
    array.append(a)
cnt = max(array)
dp = [[0]*3 for i in range(100000)]
dp[0] = [0, 0, 0]
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]
for j in range(4, cnt+1):
    dp[j][0] = dp[j-1][1] % 1000000009 + dp[j-1][2] % 1000000009
    dp[j][1] = dp[j-2][0] % 1000000009 + dp[j-2][2] % 1000000009
    dp[j][2] = dp[j-3][0] % 1000000009 + dp[j-3][1] % 1000000009
for k in range(len(array)):
    print(sum(dp[array[k]]) % 1000000009)

처음에 문제를 풀 때 너무 점화식을 찾으려 했던 경향이 있었다. 점화식을 찾는 것이 가장 간단한 방법이기는 하지만, 그게 안된다면 빠르게 문제에서 요구하는 대로 DP를 적용하여 풀어야 하는 것 같다. DP 문제를 풀다 보면 보일 것이라고 생각된다.