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

풀이

이문제는 기존 dp문제처럼 1차원으로 점화식을 구하려면
풀수가 없다.. dp문제는 꼭 1차원으로 점화식을 구하는게 아니다라는 걸 알려준 문제!

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

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

ex)dp[3]은
2 1
1 2
3
이 예시를 보면 각각 3개의 경우의 끝나는 수가 1,2,3으로 나온다!

그 후

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]

전체코드

import sys
input=sys.stdin.readline
n=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):
    dp[i][0]=dp[i-1][1]%1000000009+dp[i-1][2]%1000000009
    dp[i][1]=dp[i-2][2]%1000000009+dp[i-2][0]%1000000009
    dp[i][2]=dp[i-3][0]%1000000009+dp[i-3][1]%1000000009
for i in range(n):
    x=int(input())
    print(sum(dp[x])%1000000009)

이 문제의 핵심은 dp문제에서 점화식 구하는 과정에서 1차원으로만 접근하면 안된다는것😂😂