백준 15990 파이썬 (1, 2, 3 더하기 5)

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

💻 Code

n = int(input())

dp = [[0 for _ in range(3)] for _ 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]  + dp[i-1][2]) % 1000000009
    dp[i][1] = (dp[i-2][0] + dp[i-2][2]) % 1000000009
    dp[i][2] = (dp[i-3][0] + dp[i-3][1]) % 1000000009

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

• 단순히 1차원적으로 규칙을 찾으려하면 안되는 문제 (2차원배열 활용)

• 연속적인 숫자가 오면 안되기 때문에 1,2,3으로 끝나는 경우 세 가지를 생각해야 한다.
  

• 이해를 돕기 위해 n=10으로 두고 dp 리스트를 출력해보았다.