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

문제 바로가기

🙄 문제 이해

1, 2, 3 만을 이용해서 주어지는 수를 만들 수 있는 경우를 모두 구합니다.
문제에선 정수 4가 주어졌으며, 4를 만드는 방법은 문제에서처럼 7가지의 경우가 있습니다.

5를 만드는 경우는 13가지이며, 16가지가 아닌 이유는 4부터는 사용할 수 없기 때문에 4+1, 1+4, 5 는 해당되지 않습니다.

📝 문제 풀이

n=4일 때와 n=5일 때를 구해보면 n-1, n-2, n-3번째 수의 합이라는 규칙을 찾을 수 있습니다.
이를 통해 점화식을 구해보면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3] 임을 알 수 있습니다.

명확하게 따지자면 n=4일 때, 1+1+1+1은 n=3일때의 [1+1+1]에 +1 한 값이며, 2+1+1은 [2+1]에 +1한 값 임을 알 수 있습니다.

이 문제의 경우 숫자만으로 규칙성을 구할 수 있기에 생략했으나, 실제로는 n을 이루는 경우들이 n-1과 n-2, n-3의 경우에서 비롯되었다는 것을 알아야 합니다.

💻 Python 코드

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

t = int(input())
for _ in range(t):
    dp = [0]*11
    dp[0]=0
    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])