백준: 15991 1, 2, 3 더하기 6

1, 2, 3 더하기 시리즈

• 1, 2, 3 더하기
• 1, 2, 3 더하기 2
• 1, 2, 3 더하기 3
• 1, 2, 3 더하기 4
• 1, 2, 3 더하기 5
• 1, 2, 3 더하기 6
• 1, 2, 3 더하기 7
• 1, 2, 3 더하기 8
• 1, 2, 3 더하기 9

 

문제

15991번: 1, 2, 3 더하기 6

 

문제 풀이

 1, 2, 3의 합으로 N이라는 숫자를 나타내고자 할 때 수식이 대칭인 경우만 방법의 수로 취급하는 문제이다. 문제를 풀기 위해 N이 증가함에 따라 발생하는 경우의 수를 나열하면 아래와 같다.

 

• N은 1인 경우: 1개
  • `1`
• N은 2인 경우: 2개
  • `1 + 1`
  • `2`
• N은 3인 경우: 2개
  • `1 + 1 + 1`
  • `3`
• N은 4인 경우: 3개
  • `1 + 1 + 1 + 1`
  • `2 + 2`
  • `4`
• N은 5인 경우: 3개
  • `1 + 1 + 1 + 1 + 1`
  • `2 + 1 + 2`
  • `5`
• N은 6인 경우: 4개
  • `1 + 1 + 1 + 1 + 1 + 1`
  • `2 + 2 + 2`
  • `3 + 3`
  • `6`

 이와 같은 경우의 수를 구하고 N이 7인 경우를 구하고자 하면 `1 + 5 + 1`, `2 + 3 + 2`, `3 + 1 + 3`과 같이 양 옆으로 1, 2, 3을 붙이는 경우의 수가 존재함을 알 수 있다. 중간에 오는 숫자인 `5, 3, 1`은 앞에서 경우를 구하였으므로 `3 + 2 + 1 = 6`이라는 경우의 수를 도출할 수 있다. 이를 점화식으로 나타낸다면 `dp[N - 2] + dp[N - 4] + dp[N - 6]`이다. 즉, 점화식 앞에서 부터 양 옆으로 1, 2, 3이 붙는 경우이다.

 

코드

from sys import stdin


if __name__ == '__main__':
    MAX = 100001
    divisor = 1000000009
    dp = [0, 1, 2, 2, 3, 3, 6] + [0] * (MAX - 7)

    for i in range(7, MAX):
        dp[i] = (dp[i - 2] + dp[i - 4] + dp[i - 6]) % divisor

    t = int(stdin.readline())

    for _ in range(t):
        n = int(stdin.readline())
        print(dp[n])