[Python]9095번, 1, 2, 3 더하기

목차

 

문제

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

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

 

입력

 

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

 

출력

 

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

 

풀이

 

문제가 길지만 규칙을 찾으면 간단하다.

 

동적계획법을 위한 dp리스트를 만든다고 가정하면

 

• dp[1] = 1
• dp[2] = 2
• dp[3] = 4
• dp[4] = 7
• ...

이런 식으로 이어지는데, 이전의 세 항의 합을 다음 리스트에 저장하면 되는 식이다.

 

물론 주어진 문제의 숫자에 따라 기본값을 설정해야 하는 까다로움은 있지만,

 

동적계획법에 익숙해지기 편한 좋은 문제라는 생각이 든다.

 

바로 코드를 보자.

 

Python

 

import sys

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    dp = [0] * (n + 1)

    if n >= 1:
        dp[1] = 1
    if n >= 2:
        dp[2] = 2
    if n >= 3:
        dp[3] = 4

    for i in range(4, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    print(dp[n])

주어진 T개의 숫자 n에 대해 각 과정을 나타낸 것이다.

 

n이 1, 2, 3일 경우에만 기본값을 설정해 주면 그 다음은 피보나치 수열의 변형 버전에 불과하다.

 

오랜만에 동적계획법 문제를 푸니 이제야 조금 익숙해지는 기분이 든다.

 

9095번, 1, 2, 3 더하기, 끝!