백준 9095: 1,2,3 더하기 (DP)

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

특정 숫자를 주어진 정수들의 합으로 나타낼 수 있는 경우의수를 구하는 문제. 

다이나믹 프로그래밍 기본문제이다. 

정수 4를 1,2,3의 합으로 나타내는 모든 방식은 다음과 같다. 

 

정수 n은 양수이며 11보다 작다고 주어졌으므로 1부터 구해본다면,

1을 나타내기 위해서는 1만 필요하기때문에 => 1가지 

2를 나타내기 위해서는 (1+1), (2) => 2가지

3을 나타내려면 (1+1+1), (1+2), (2+1), (3) => 4가지 

 

예제에서 주어진 4를 나타내기 위해서는 위의 1~3까지의 가지수를 모두 합하면 된다. 

 

5을 나타내보면,

(1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1,), (2,1,1,1), (1,1,3), 

(1,3,1), (3,1,1), (1,2,2), (2,2,1), (2,1,2), (2,3), (3,2) => 13가지

13 = 2+4+7로부터 계산된것. 이를 구현하기 위해 다음과 같은 점화식을 사용했다. 

n = int(input())

def solution(x):
  if x == 1:
    return 1
  elif x == 2:
    return 2
  elif x == 3:
    return 4
  else:
    return solution(x-1) + solution(x-2) + solution(x-3)
for i in range(n):
  x = int(input())
  print(solution(x))