[백준][Python][15989][DP] 1,2,3더하기 4

문제 : https://www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

DP 문제인데 좀 까다롭다. 

 

1,2,3 더하기 시리즈를 보면 하나같이 DP 문제인데, 이문제가 제일 어려웠다.

 

1,2,3을 써서 숫자를 만드는데, 숫자는 같으면서 순서만 다른건 하나로 하는 것이다.

밑에는 기본적으로 손으로 계산할만한 초기값이다

1. 1 만들기 ->1
2. 2 만들기 -> 1+1, 2
3. 3 만들기 -> 1+1+1, 2+1, 3

그럼 4 만들기는 어떻게 할까?

생각해보면, 1,2,3 쓰는 갯수는 무한이므로 다음과 같이 생각해 볼 수 있다.

 

• 3 + (1 만드는 갯수)
• 2 + (2 만드는 갯수)
• 1 + (3 만드는 갯수)

이렇게 하면 된다. 숫자 쓴것은 같고 순서만 다른건 1개로 하기 때문에 밑의 방식이 가능하다.

 

그럼 5는?

 

• 4 + (1 만드는 갯수)
• 3 + (2 만드는 갯수)
• 2 + (3 만드는 갯수)

 

 

6,7,8...n 을 생각해 보면 다음과 같다.

 

n을 만드는 갯수 : 

 

• n-1 + (1 만드는 갯수)
• n-2 + (2 만드는 갯수)
• n-3 + (3 만드는 갯수)

따라서, DP 배열을 만드는데 DP[만들려는 숫자][1,2,3] 을 만들면 되지 않을까? 해서 만든 코드이다.

 

import sys
n = int(input())

for _ in range(n):

    dp = [[1,0,0],[1,1,0],[1,1,1]]

    a = int(input())
    if a<=3:
        print(sum(dp[a-1]))
        continue
    for i in range(3, a+1):
        tmp = []
        tmp.append(dp[i-1][0])
        tmp.append(dp[i-2][0]+dp[i-2][1])
        tmp.append(dp[i-3][2]+dp[i-3][1]+dp[i-3][0])

        dp.append(tmp)

    print(sum(dp[a-1]))