[102일차] 1, 2, 3 더하기 - 백준 - 9095(python - 다이나믹 프로그래밍)

문제 설명

정수 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의 합으로 나타내는 방법의 수를 출력한다.

 

예제 입력, 예제 출력

3 4 7 10

7 44 274

 

코드 및 설명

n = int(input())
dp = [0, 1, 2, 4] + [0] * (7)

for i in range(4, 11):
  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
for j in range(n):
  t = int(input())
  print(dp[t])

 

이 문제도 DP 문제이다. 1, 2, 3의 합으로 정수 n을 만들 수 있는 경우의 수를 찾는 것이다.

정수n 경우의 수	1	2	3	4
1	1	1+1	1+1+1	1+1+1+1
2		2	2+1	2+1+1
3			1+2	1+2+1
4			3+1	3+1
5				1+1+2
6				2+2
7				1+3
	1	2	4	7

 

n = 1이면 1로 1을 만들 수 있으니 1개

 

n = 2이면 1+1, 2로 만들 수 있으니 2개

 

n = 3이면 1+1+1, 2+1, 1+2, 3+1로 만들수 있으니 4개

 

3보다 커지는 수 부터는 123의 합을 전부 넣어서 경우의 수를 구할 수 있기 때문에 여기서 점화식을 만들어봐야한다.

 

3 에서 1+1+1+1 =4 , 2+1+1 = 4 , 1+2+1 = 4, 3+1 => 4개

2에서 1+1+2 = 4, 2+2 = 4 => 2개

1에서 1+1+1+1 = 4 => 1개

 

총 7개가 된다. 

 

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이 된다.

 

11보다 작은 수 이기때문에 미리 계산해놓아도 시간은 충분하다.