[백준 9095번] 1, 2, 3 더하기 (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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

기록

(dp 3일차) 여러 개의 테스트케이스가 입력으로 들어오기 때문에 기존에 n까지의 배열을 만들었던 방법과 다르게 풀어야해서 당황했었다. 가장 큰 테스트케이스로 배열을 만들어야하나, Top-down방식으로 배열을 만들어나가야 하나하다가 n이 12로 제한되어있는 조건을 보고 처음에 배열을 만들어 놓기로 했다.

 

이 문제는 n을 1,2,3의 합으로 나타내는 방법 수를 저장하는 배열 dp를 만들어, dp[n] = dp[n-1]+dp[n-2]+dp[n-3]로 점화식을 세우면 된다. (=가능한 3가지 연산(+1, +2, +3)의 경우의 수를 모두 더하는 식)

 

코드

from sys import stdin

T = int(input())
dp = [0, 1, 2, 4]
for i in range(4, 13):
    dp.append(sum(dp[-3:]))

for _ in range(T):
    print(dp[int(input())])

1. n을 1,2,3의 합으로 나타내는 방법 수를 저장하는 배열 dp를 만들어 n이 1, 2, 3일 때의 경우를 초기화한다.

2. dp[n-1](1을 더하는 연산), dp[n-2](2를 더하는 연산), dp[n-3](3을 더하는 연산)의 경우의 수를 더하여 dp에 저장한다.

3. 각 테스트케이스에 해당하는 수를 dp에서 찾아 출력한다.