[Python] 백준 9095 1, 2, 3 더하기 문제풀이 및 정답

 

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

 

문제풀이

본 문제는 간단한 DP 알고리즘의 문제였다.

DP 문제를 해결하기 위해선 초기항과 점화식이 필요하다. 하지만 이번 문제는 쉽게 생각해낼 수 있는 수준이었다.

일단, 우리가 사용할 수 있는 수식에서의 숫자는 1, 2, 3이다. 여기서 초기항이 3개까지 작성되야 한다는 것을 알 수 있다.

 

되게 간단한 개념인데, DP 배열을 선언하고 해당 배열의 각 인덱스에는 해당 인덱스 숫자를 만들기 위한 수식의 최대 개수가 들어간다.

예를 들어서 2번 인덱스에는 2를 만들 수 있는 수식의 최대 개수가 들어간다.

여기서 2를 만들기 위해선 1+1, 2로 총 2개가 있다.

 

이러한 방식으로 1번항과 3번항을 만들면 문제를 해결하기 위한 준비가 모두 끝이 난다.

 

자 한 번 확인해보자.

 

우리가 5라는 숫자를 만들기 위해선 많은 경우의 수가 있고, 이를 계산하기는 조금 복잡할 것이다.

하지만 생각을 조금 바꿔보자. 더 작은 숫자에 1, 2, 3을 더하면 5라는 숫자를 만들 수 있지 않나?

 

예를 들어서 3을 만들 수 있는 경우들에 모두 마지막 수식에 2를 더해주면 5를 만드는 수식이 만들어진다.

동일한 방식으로 4를 만드는 경우에도 1을 더하고, 2를 만드는 경우에도 3을 더하면 된다.

 

이 모든 것은 5를 만드는 경우의 수와 동일하게 된다.

 

즉, 이전 항, 전전항, 전전전항의 총 세개의 합산이 현재의 숫자를 만들기 위한 수식의 개수인 것이다.

 

이것을 점화식으로 풀어본다면 아래와 같다.

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

 

위의 점화식으로 문제를 다시 접근해보면 쉽게 해결할 수 있다.

본인은 이번 문제를 Bottom-Up 방식으로 숫자 4부터 순차적으로 DP배열을 만들어나갔다.

 

정답코드

t = int(input())

for _ in range(t):
    n = int(input())
    dp = [0 for _ in range(n+1)]
    
    if n < 3:
        print(n)
    elif n == 3:
        print(4)
    else:
        dp[1] = 1
        dp[2] = 2
        dp[3] = 4
        
        for i in range(4, n+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        
        print(dp[n])