[Python] 백준 9095번: 1, 2, 3 더하기 풀이

 

소스코드

T = int(input())
for i in range(T):
    dp = [0,1,2,4]
    n = int(input())
    for j in range(4,n+1):
        dp.append(dp[j-3] + dp[j-2] + dp[j-1])
    print(dp[n])

0 -> 0개

1 = 1 -> 1개

2 = 1 +1  -> 2개

   = 2

3 = 1 + 2  -> 4개

   = 2 + 1

   = 3

   = 1 + 1 + 1

까지는 쉽게 구할 수 있다.

 

그렇다면 4는? 

크게 세 가지 방법으로 1 + 3 / 2 + 2 / 3 + 1 이 있다.

왜냐면 1,2,3의 합으로 표시를 하는 것이므로 항상 1 + (n-1) / 2 + (n-2) / 3 + (n-3)

으로 구할 수 있는 것이다!!

그렇다면 밑줄 친 3, 2, 1 을 또 여러가지 1,2,3 을 이용해 구할 수 있을 것인데, 

그것은 앞에서 미리 구해놓았다. 1은 1개, 2는 2개, 3은 4개!!

즉, 1 + 3 -> 4개

2 + 2 -> 2개

3 + 1 -> 1개

이므로 4에 대한 방법의 수는 총 7이다.

 

이렇게 작은 숫자부터 n까지 상향식 접근을 통해 구할 수 있다.

5또한 마찬가지로 (3과 더했을 때)2의 방법수(2개) + (2와 더했을 때)3의 방법수(4개) + (1과 더했을 때)4의 방법수(7개) = 13개임을 알 수 있다.

 

n = 1 + (n-1) -> dp[n-1]

n = 2 + (n-2) -> dp[n-2]

n = 3 + (n-3) -> dp[n-3]

따라서 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 로 쉽게 구할 수 있는 문제이다.