백준 알고리즘 - 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의 합으로 나타내는 방법의 수를 출력한다.

 

나의 코드

# 정수 n 입력
number=int(input())

Testcase=[] # 테스트 케이스 초기화
for i in range(number): # 정수 n 만큼의 테스트 케이스 생성
    Testcase.append(int(input()))

f=[1,2,4] # f(1)=1, f(2)=2, f(3)=4

# DP
for i in range(3,max(Testcase)):
    f.append(f[i-1]+f[i-2]+f[i-3]) # 점화식

for i in Testcase:
    print(f[i-1])

해설

정수 1을 1, 2, 3의 합으로 나타낼 수 있는 방법은 1 한가지이다. 정수 2를 1, 2, 3의 합으로 나타낼 수 있는
방법은 1+1, 2로 2가지이다.

1 = (1)
2 = (1+1), (2)
3 = (1+1+1), (1+2), (2+1), (3)
4 = (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2), (1+3), (3+1)
5 = (1+1+1+1), (1+1+1+2), (1+1+2+1), (1+2+1+1), (2+1+1+1), (1+2+2), (2+1+2), (2+2+1),
(1+1+3), (1+3+1), (3+1+1), (2+3), (3+2)

전형적인 DP 문제이다. 
1. 큰 문제를 작은 문제로 나눌 수 있으며 

2. 작은 문제에서 구한 값은 큰 문제에서도 동일한 값이다

 

만들고자 하는 숫자의 값이 증가하면 만들 수 있는 경우의 수도 증가하는데 이전에 사용했던 숫자의 경우의 수가
사용되고 있으므로 두가지 가정을 모두 만족한다.

이러한 패턴이 보이므로 점화식을 써볼 수 있다.
f(n)을 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 총 방법 수라고 한다면 f(n) = f(n-1) + f(n-2) + f(n- 3) 으로 나타낼 수 있다. 물론 n은 3보다 커야 한다. f(1)=1, f(2)=2, f(3)=4 이며 이러한 점화식으로 코드를 완성할 수 있다.