[백준 알고리즘/Python] 15990 1,2,3 더하기 5

문제

 

문제이해

dp[1]	1		1개
dp[2]	2		2개
	1+1
dp[3]	3		4개
	1+2 2+1 1+1+1	dp[2]에 1 더해주기
dp[4]	1+3 3+1 1+2+1 2+1+1 1+1+1+1	dp[3]에 1 더해주기	7개
	2+2 1+1+2	dp[2]에 2 더해주기
dp[5]	1+3+1 3+1+1 1+2+1+1 2+1+1+1 1+1+1+1+1 2+2+1 1+1+2	dp[4]에 1 더해주기	13개
	3+2 1+2+2 2+1+2 1+1+1+2	dp[3]에 2 더해주기
	2+3 1+1+3	dp[2]에 3 더해주기

여기에서 중복을 제외해야 합니다.

5를 예를 들면

dp[4]에서 마지막 값이 1인 것은 제외해야합니다.

dp[3]에서 마지막 값이 2인 것은 제외해야합니다.

dp[2]에서 마지막 값이 3인 것은 제외해야합니다.

 

즉, 2차원 배열을 사용해야 합니다.

dp[i][1], dp[i][2], dp[i][3]인 상태를 모두 기록해야 합니다.

 

   0,    1,   2,   3 끝자리가 인수

1[ 0,    1    0    1]

2[ 0,    0    1    0]

3[ 0,    1    1    1]

4[ 0,    2    0    1]

5[ 0,    1    2    1]

 

점화식은 

dp[i][1] = dp[i-1][2] + dp[i-2][3] (끝자리가 1이면 2와 3인 상태만 허용)

dp[i][2] = dp[i-2][1] + dp[i-2][3] (끝자리가 2이면 1와 3인 상태만 허용)

dp[i][3] = dp[i-3][1] + dp[i-3][2] (끝자리가 3이면 1와 2인 상태만 허용)

 

코드

import sys

num=int(sys.stdin.readline())

d = [[0] * 4 for _ in range(100001)]

d[1] = [0,1,0,0]
d[2] = [0,0,1,0]
d[3] = [0,1,1,1]


for i in range(4,100001):
    d[i][1] = (d[i-1][2]+d[i-1][3])% 1000000009
    d[i][2] = (d[i-2][1]+d[i-2][3])% 1000000009
    d[i][3] = (d[i-3][1]+d[i-3][2])% 1000000009


for _ in range(num):
    act_num = int(sys.stdin.readline())
    print((sum(d[act_num])) % 1000000009)

여기서 d의 1,2,3을 이전값으로 더하는 과정에서 1000000009의 나머지값을 나눠주지 않으면 시간초과가 납니다.