백준-9095-1, 2, 3 더하기

구현

• 1,2,3으로 더할 수 있는 케이스를 숫자별로 나열해보면 아래와 같다.

숫자 : 개수  : 케이스
1    :  1   :  1
2    :  2   :  1 1 , 2
3    :  4   :  1 1 1 , 1 2 , 2 1 , 3
4    :  7   :  1 1 1 1 , 1 1 2 , 1 2 1 , 2 1 1 , 2 2 , 1 3 , 3 1
5    :  13  :  1 1 1 1 1 , 1 1 1 2 , 1 1 2 1 , 1 2 1 1 , 2 1 1 1 , 2 2 1 , 2 1 2 , 1 2 2 , 2 3 , 3 2 , 3 1 1 , 1 3 1 , 1 1 3

 

• 숫자 4, 5 부터 규칙이 보이기 시작한다.

규칙
4는 1+2+3 = 7개
5는 2+3+4 = 13개
    '
    '
    '

 

• 이를 점화식으로 바꾸어 보면 아래와 같이 만들 수 있다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

---

코드

T = int(input())

for _ in range(T):
    # 입력될 n은 1~10
    dp = [0 for i in range(11)]

    # 점화식에 따라 1,2,3은 고정
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

    n = int(input())

    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
    print(dp[n])

 

DP를 공부한 후 개념을 적용해볼 수 있는 좋은 문제였던 것 같다.

 

문제링크