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

 

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

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

 

예제 입력 3 4 7 10

예제 출력 3 9 27

 

풀이

 

두 수를 연속으로 사용하지 못하는 데에 초점을 두어야 한다.

 

수 n을 만들 수 있는 경우의 수는 3가지이다.

 

• 2, 3으로 시작하는(n-1)의 경우의 수
• 1, 3으로 시작하는(n-2)의 경우의 수
• 1, 2로 시작하는(n-3)의 경우의 수

 

예를 들어 6을 만든다고 가정해보자.

 

1 + 5를 만들 수 있는 경우의 수,

2 + 4를 만들 수 있는 경우의 수,

3 + 3을 만들 수 있는 경우의 수 

 

이렇게 3 가지를 찾으면 되는데 문제는 각각의 수의 경우의 수가 어느 수로 시작할 지 모르는 것이다.

따라서 dp를 2차원으로 구성해 1, 2, 3 각각 어떤 수로 시작하는 경우의 수인지 메모이제이션할 것이다.

 

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

필자는 위와 같이 4까지의 경우의 수를 담았다.

이제 수가 겹치지 않게 경우의 수를 아래 점화식과 같이 가져오면 된다.

 

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

 

import sys
input = sys.stdin.readline

dp = [[0,0,0],[1,0,0],[0,1,0],[1,1,1],[2,0,1]]
for _ in range(int(input())):
    n = int(input())
    for i in range(len(dp),n+1):
        dp.append([(dp[i-1][1]+dp[i-1][2])%1000000009,
                   (dp[i-2][0]+dp[i-2][2])%1000000009,
                   (dp[i-3][0]+dp[i-3][1])%1000000009])
    print(sum(dp[n])%1000000009)