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

 

난이도

Silver 3

입력 조건

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

 

 

출력 조건

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

입력 예시 

3
4
7
10

 

출력 예시 

7
44
274

처음 짠 코드

import sys
t = int(input())

for _ in range(t):
    num = int(sys.stdin.readline())
    d = [0] * (num+1) # index수 까지 만들 수 있는 경우의 수를 담고 있는 DP 테이블
    if num>=1:
        d[1] = 1
    if num >=2:
        d[2] = 2
    if num >=3:
        d[3] = 4
    if num>=4:
        for i in range(4,num+1):
            d[i] = d[i-1] + d[i-2] + d[i-3]
    print(d[num])

 

느낀 점

다이나믹 프로그래밍을 공부하면서 거의 처음으로 풀어본 문제이다.

다이나믹 프로그래밍의 풀이 방법은 우선 이 문제의 시간제한이 촉박해서 다른 여타 방법으로 풀 수 없는 문제일 때

다이나믹 프로그래밍으로 풀 수 있는지부터 파악할 수 있는 능력이 중요한 것 같다.

 

이후 DP 테이블을 잘 정의해야 한다. 

DP 테이블의 엄밀한 정의도 없이 막 쓰면 내가 뭘 하려고 하는 건지 까먹을 수 있다.

이후 문제에서의 규칙을 찾아 점화식을 만들고 구현하면 된다.