[백준15990] 1, 2, 3 더하기 5

문제

---

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

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

 

생각의 흐름

---

이전에 포스팅한 1, 2, 3 더하기 3과 유사하지만 차이점은 더할 때 같은 숫자가 연속으로 나오는 경우는 가짓수에 포함하지 않는다는 것이다. 그럼 이를 어떻게 구별해내야 하는가?

단순히 생각해보면 된다. 예컨대, 4를 만드는 가짓수를 구한다고 하자. 이 경우 가능한 case는 1, 2, 3을 만드는 case들에 각각 끝에 3, 2, 1을 더해주어서 만들어야 한다. 근데 이 때 주의할 점은 3을 더할때는 1을 만드는 case들 중에 끝에 3이 오는 경우는 배제해주어야 한다. 2, 1을 더해줄 때도 마찬가지이다.

해서, dp[i][j]가 i를 만드는데 더해줄 때 끝에 오는 수가 j인 경우의 수를 담는다고 하면 i=4인 경우,

dp[4][1] = dp[3][2] + dp[3][3]

dp[4][2] = dp[2][1] + dp[2][3]

dp[4][3] = dp[1][1] + dp[1][2]

가 된다.

 

코드

---

# 백준 15990

t = int(input())
dp = [[0]*4 for _ in range(100001)]

# dp[i][j] : i를 만드는 데 더해지는 끝 수가 j인 경우의 수
dp[1][1] = 1
dp[2][2] = 1
dp[3][1], dp[3][2], dp[3][3] = 1, 1, 1

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

for _ in range(t):
    n = int(input())
    print(((dp[n][1]+dp[n][2])%1000000009+dp[n][3])%1000000009)