[백준] 9095번 문제 (1, 2, 3 더하기) 파이썬(Python) 풀이

for _ in range(int(input())):

    n = int(input())
    dp = [0] * 11
    dp[1], dp[2], dp[3] = 1, 2, 4

    for i in range(4, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    print(dp[n])

 

해당 숫자 n에 대하여 경우의 수를 나타내면 아래 표와 같다.

n	n에 대한 경우의 수
1	1
2	2
3	4
4	7
5	13
6	24
7	44
8	81
9	149

표를 보면 dp[i]에 대하여

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 라는 식이 성립한다.

 

따라서, 최대 입력은 10이기 때문에 10까지 경우의 수를 미리 구해놓고 dp[n]을 출력해줬다.