[DP] 15990번 1,2,3 더하기 5

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

알고리즘

• Dynamic Programming

풀이

포인트

• 같은 숫자를 여러번 사용할 수 있지만 연속적으로 사용할 수 없다는 점

Dynamic Programming

같은 숫자를 연속적으로 사용할 수 없다는 점에 착안하여, DP 테이블을 2차원으로 정의한다.

• $dp[i][j]$: 맨 마지막 수가 $j$면서

정수 $i$를 만들 수 있는 경우의 수

• $1+2+2$: $dp[5][2]$에 포함되는 경우의 수임

• 점화식

  • $j == 1$이면, $dp[i][j] = dp[i-j][2] + dp[i-j][3]$
  • $j == 2$이면, $dp[i][j] = dp[i-j][1] + dp[i-j][3]$
  • $j == 3$이면, $dp[i][j] = dp[i-j][1] + dp[i-j][2]$

같은 숫자를 연속적으로 사용할 수 없으므로 끝 수가 $j$일 때, $j$를 제외한 나머지 숫자로 끝나는 경우의 수를 더해준다.

[Source Code]

m = 100000
numbers = [1,2,3]
dp = [[0]*4 for _ in range(m+1)]
for j in numbers:
    dp[j][j] = 1
for i in range(1,m+1):
    for j in range(1,4):
        if i-j >= 0:
            if j == 1:
                dp[i][j] += dp[i-j][2] + dp[i-j][3]
            if j == 2:
                dp[i][j] += dp[i-j][1] + dp[i-j][3]
            if j == 3:
                dp[i][j] += dp[i-j][1] + dp[i-j][2]
        dp[i][j] %= 1000000009

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