[Baekjoon]백준 9095 1, 2, 3 더하기(실버 3) - Python

문제설명

문제를 살펴보면 문제 자체는 간단하다 어떠한 수를 완성하기 위해 가능한 경우의 수를 구하면 된다

이 문제를 보자말자 들었던 생각으로는 나눠서 생각하면 더 간단하고, 그러면 동적 프로그래밍(dp)를 사용하면

되겠다! 라는 생각이 들었다 그래서 어떠한 규칙이 존재하는지 확인해보았다

dp[1] = 1  : 1

dp[2] = 2 : 1+1, 2

dp[3] = 4 : 1+1+1, 1+2, 2+1, 3

dp[4] = 7 : 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1

dp[5] = 13 : 1+1+1+1+1, 1+2(2의 위치에 따라 달라지므로 총 5개), 2+2+1(같은 원리로 3개), 3+1+1(같은 원리로 3개), 3+2

...

가만히 보다보니 반복되는 규칙을 직관적으로 발견할 수 있었다

dp[4] = dp[3] + dp[2] + dp[1], dp[5] = dp[4] + dp[3] + dp[2]

왜 그런 규칙이 생기는지 생각해보면 특정 숫자를 만들기위해 필요한 경우는 문제에서 조건으로 이루어진 1, 2, 3을

더한 경우 만들어진다 다시 말하자면 10을 구하고자한다면 7에 3을 더하는 경우, 8에 2를 더하는 경우, 9에 1을 

더하는 경우 총 3가지 경우의 수의 합이 10을 구하는 경우의 수가 된다(문제 조건이 1, 2, 3이기 때문)

이를 쪼개서 생각해보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 이라는 규칙이 완성된다

import sys
input = sys.stdin.readline

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