[백준] 9095번:1, 2, 3 더하기 (python 파이썬)

문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

풀이

입출력 예제를 보면 바로 규칙을 알 수 있다.

4일 때, 7

7일 때, 44

10일 때, 274

1~3 일 때는 쉽게 계산이 가능하다.

1 -> 1

2 -> 2

3 -> 4

4 -> 7

5 -> ?

6 -> ?

7 -> 44

여기서 5까지만 구해봤다. 5일 때 13개가 나왔다.

그렇다면,

1 -> 1

2 -> 2

3 -> 4

4 -> 7

5 -> 13

6 -> ?

7 -> 44

이제 규칙이 보일 것이다 !

dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 인 것을 알 수 있다.

확실하게 알기 위해 6일 때를 구해보면 4+7+13 = 24이고, 그렇게 되면 7일 때 44가 나오므로, 확신할 수 있다.

소스코드

import sys
input = sys.stdin.readline

t = int(input())
flg = 3
dp = [0]*11
dp[1] = 1
dp[2] = 2
dp[3] = 4
for _ in range(t):
    n = int(input())
    if n <= flg:
        print(dp[n])
        continue
    nowflg = flg
    for i in range(nowflg+1, n+1):
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
        flg += 1
    print(dp[n])