[Python/파이썬 15990 백준] 1, 2, 3 더하기 5

www.acmicpc.net/problem/15990

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

풀이

1차원으로 계속 규칙을 찾으려니

30분정도 봤는데 못찾았다.. 어렵네용...

 

답을 참고해서 이해한 내용을 적자면

 

dp [1], dp[2], dp[3]에

각각 1,2,3으로 끝나는 상황을 넣는다.

ex) dp[3] 은

2 1 

1 2

3

이 예시와 같이 끝나는 숫자가 1일때 2일때 3일때 각각 1개씩이다

 

그 후

n이 만약 6인 상황에서

dp[5]에서 2로 끝난거 +1을 해주거나, 3으로 끝난거에 +1을 해주면 -> dp[6][0]

dp[4]에서 1로 끝난거에 +2 or 3으로 끝난거에 +2 -> dp[6][1]

dp[3]에서 1 or 2로 끝난거에 +3 을 해주면 -> dp[6][2]

 

-> 정리하면

dp[i][0] = dp[i-1][1] + dp[i-2][2] 

dp[i][1] = dp[i-2][0] + dp[i-2][2] 

dp[i][2] = dp[i-3][0] + dp[i-3][1] 

# dp
# 1차원으로 생각 해보니 절대 안됐다...
# 답 보니 2차원으로 쪼개서 생각
# 1,2,3으로 끝난 갯수를 세고 그 뒤에 해당하는 숫자 붙이기

import sys
input=sys.stdin.readline

tc=int(input())

dp=[[0 for _ in range(3)] for i in range(100001)]

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

for i in range(4,100001):
    # 6일때 만약

    # 5에서 2와 3으로 끝난거에 1 붙이기
    dp[i][0]=dp[i-1][1]%1000000009+dp[i-1][2]%1000000009
    # 4에서 1과 3으로 끝난거에 2붙이기
    dp[i][1]=dp[i-2][0]%1000000009+dp[i-2][2]%1000000009
    # 3에서 1과 2로 끝난거에 3붙이기
    dp[i][2]=dp[i-3][0]%1000000009+dp[i-3][1]%1000000009

for i in range(tc):
    n=int(input())
    print(sum(dp[n]) % 1000000009)