[python] 9095, 1, 2, 3 더하기 : 다이나믹 프로그래밍(DP)

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

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을 1, 2, 3의 합으로 나타내는 방법의 수 구하기

💡 풀이 포인트

 DP의 가장 기본적인 구조를 사용하는 문제이다. 1, 2, 3의 합으로 4 이상의 수까지 나타내야 하기 때문에 1, 2, 3에 대한 경우의 수를 먼저 정의해준다면 쉽게 접근할 수 있는 문제였다.

 

• 1 = 1 : 한 가지
• 2 = 2 = 1 + 1 : 두 가지
• 3 = 3 = 1 + 2 = 2 + 1 = 1 + 1 + 1 :네 가지

4 이상의 수들은 위의 수들만을 조합해 더해지므로, 만약 구하고자 하는 수를 N이라 할 때 아래의 조건이 성립한다.

( 1 ) N - 1에서 + 1 -> N - 1을 만드는 경우의 수와 동일하므로 dp[N - 1]

( 2 ) N - 2에서 + 2 -> N - 2를 만드는 경우의 수와 동일하므로 dp[N - 2]

( 3 ) N - 3에서 + 3 -> N - 3를 만드는 경우의 수와 동일하므로 dp[N - 3]

따라서, 이를 점화식으로 표현하면,

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

 

t = int(input())
fn = [0, 1, 2, 4]

for _ in range(t):
  n = int(input())
  if n <= 3:
    print(fn[n])
  else:
    dp = fn + [0] * (n - 3)
    for i in range(4, n + 1):
      dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    print(dp[n])

t = int(input())

for _ in range(t):
  n = int(input())
  fn = [0, 1, 2, 4]
  if n <= 3:
    print(fn[n])
  else:
    for i in range(4, n + 1):
      fn.append(fn[i - 1] + fn[i - 2] + fn[i - 3])
    print(fn[n])