[백준] Silver 3. 9095 - 1, 2, 3 더하기 python

문제 링크

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

---

문제 설명

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

---

제출 코드

import sys

input = sys.stdin.readline

for _ in range(int(input().rstrip())):
    n = int(input().rstrip())
    dp = [0,1,2,4]
    if n > 3:
        for i in range(4,n+1):
            dp.append(dp[i-1] + dp[i-2] + dp[i-3])
    print(dp[n])

 

풀이

• 점화식을 찾아서 풀면 되는 문제
• 기본적으로 3까지 1, 2, 3의 합으로 나타내는 방법의 가짓수를 저장해둔다.
  • 1: 1
  • 2: 1+1, 2
  • 3: 1+2, 1+1+1, 2+1, 3
• 4: (1만드는 방법+3) 1+3, (2만드는 방법+2) 1+1+2, 2+2, (3만드는 방법+1) 1+2+1, 1+1+1+1, 2+1+1, 3+1 으로 나타낼 수 있다
  • 즉, 현재 수보다 1, 2, 3 작은 수를 만드는 가짓수를 더해주면 현재 수를 만드는 가짓수가 된다.
  • 점화식 : dp[n] = dp[i-1] + dp[i-2] + dp[i-3]

알아둘 사항

• 점화식을 찾기 위해서는 조건에 맞춰서 앞에서부터 직접 계산을 해보면 쉽게 발견할 수 있다.