[백준] #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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력

3
4
7
10

예제 출력

7
44
274

백준 9095번 문제

💡Idea

DP를 사용하여 풀면 해결되는 문제입니다.

정수 n에 따른 값들 사이의 점화식을 찾아 구현해보았습니다.

• n이 1인 경우 : 1 (1)
• n이 2인 경우 : 2 (1+1, 2)
• n이 3인 경우 : 4 (1+1+1, 1+2, 2+1, 3)
• n이 4인 경우 : 7 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1)

위와 같이 값들 사이의 관계를 찾아보니, 아래와 같은 점화식을 얻을 수 있었습니다.

$P_n = P_{n-1}+P_{n-2}+P_{n-3}$

💻코드

• ⏰ 시간 : 68 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline

dp = [0 for _ in range(11)]
dp[1], dp[2], dp[3] = 1, 2, 4 # DP를 위한 초깃값 설정

for i in range(4, 11): # n이 4일 때부터 11까지의 값 계산
    dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]

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