[파이썬] 백준 9461 : 파도반 수열

[파이썬] 백준 9461 : 파도반 수열

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

실버 3

수학, DP

---

숫자들을 쭉 깔아서 보면 바로 규칙이 보일 것이다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9...

i번째의 값은 i-3과 i-2번째의 값의 합으로 이루어져있는 피보나치 수열과 비슷한 규칙을 가지고 있다.

 

import sys; input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N = int(input())
    dp = [1] * 101
    for i in range(4, N+1):
        dp[i] = dp[i-3] + dp[i-2]
    print(dp[i])

 

DP문제 중에 이게 제일 쉬운 문제인듯 싶다. 보자마자 답이 생각나는데 이게 진짜 맞는지 계속 의심했다.