[백준] 9095. 1, 2, 3 더하기 - 파이썬

[Silver III]

 

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

풀이

간단한 Dynamic Programming 문제.

n이 11보다 작다 는 조건이 걸려 있어, Top-Down 방식으로 재귀를 이용해 풀어도 시간초과나, Recursion 기본 횟수(1000회) 제한에 걸리지 않을 법 한 문제였다.

 

[정수 k를 1, 2, 3의 합으로 나타내는 방법의 수]

= [k-1을 나타내는 방법의 수] + [k-2을 나타내는 방법의 수] + [k-3을 나타내는 방법의 수]

라는 것만 캐치한다면, Bottom-Up 방식으로 Memoization 하며 나아가면 된다.

 

k-1 에서 k를 만드는 방법은 (k-1) + 1 한 가지가 존재.

k-2 에서 k를 만드는 방법은 (k-2) + 1 + 1, (k-2) + 2 두 가지가 존재하나, 전자는 이미 k-1에서 k를 만드는 방법에 포함되어 있는 방법이기 때문에, 한 가지만 count.

마찬가지로, k-3 에서 k를 만드는 방법은 (k-3) + 1 + 1 + 1, (k-3) + 1 + 2, (k-3) + 2 + 1, (k-3) + 3 으로 네 가지가 존재하나, 앞의 3가지 방법은 k-1에서 k를 만드는 방법, k-2에서 k를 만드는 방법의 개수에 포함되어 있으므로, 마지막 한 가지만 count.

k-4 에서 k를 만드는 방법은 k-4에 1을 더하든, 2를 더하든, 3을 더하든, 위의 3가지(k-3 -> k / k-2 -> k / k-1 -> k)의 경우에 포함되므로, 제외한다.

따라서, [정수 k를 1, 2, 3의 합으로 나타내는 방법의 수] = [k-1을 나타내는 방법의 수] + [k-2을 나타내는 방법의 수] + [k-3을 나타내는 방법의 수] 가 된다.

 

T = int(input())

# dp[k]는 정수 k를 1, 2, 3의 합으로 나타내는 방법의 수를 저장.
dp = []
dp.append(0)    # dp[0] = 0
dp.append(1)    # dp[1] = 1
dp.append(2)    # dp[2] = 2
dp.append(4)    # dp[3] = 4

for k in range(4, 12):
    # dp[k-3]+dp[k-2]+dp[k-1] = dp[k]
    dp.append(dp[k-3]+dp[k-2]+dp[k-1])

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