[백준] 15990 - 1, 2, 3 더하기2 in 파이썬

문제 출처

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로 나눈 나머지를 출력한다.

---

문제 풀이

이전의 1,2,3더하기 문제에서 같은 수를 연속해서 쓸 수 없다는 제약 조건이 추가된 문제이다.

[백준] 9095 - 1, 2, 3 더하기 in 파이썬

 

이전 문제의 경우의 수는 다음과 같았다.

  1. +1 할 수 있는 경우 : dp[n-1]

  2. +2 할 수 있는 경우 : dp[n-2]

  3. +3 할 수 있는 경우 : dp[n-3]

 

연속되면 안된다는 조건이 추가되었으므로, 각각의 경우의 수에 추가적인 작업이 필요하다.

  1. dp[n-1] 중에서도 2,3으로 끝난 경우의 수

  2. dp[n-2] 중에서도 1,3으로 끝난 경우의 수

  3. dp[n-3] 중에서도 1,2으로 끝난 경우의 수

를 따져서 합해야 원하는 값을 얻을 수 있다.

 

즉, 끝자리 수가 어떻게 끝나는 지를 이차원 배열을 활용해서 저장시켜줘야 계산할 수 있다.

예) dp[4][0] : N=4일때 끝자리가 1인 경우

      dp[4][1] : N=4일때 끝자리가 2인 경우

      dp[4][2] : N=4일때 끝자리가 3인 경우

(인덱스 배열이 0으로 시작하는 것과 1,2,3이 혼동이 온다면 0인덱스는 버리는 값으로 숫자를 맞춰줘도 될 것이다.)

 

작성 코드

import sys
input = sys.stdin.readline
MOD = 1000000009

tc = int(input())

dp = [[0] * 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] % MOD) + (dp[i-1][2] % MOD)
    dp[i][1] = (dp[i-2][0] % MOD) + (dp[i-2][2] % MOD)
    dp[i][2] = (dp[i-3][0] % MOD) + (dp[i-3][1] % MOD)

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