[백준 9461] 파도반 수열 - python (solved.ac - 실버 3)

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

9461번: 파도반 수열

풀이

문제를 보았을때 알수있는 힌트

문제를 보면 p의 변수가 커질수록 값이 증가하는 모습을 볼 수 있다. 또한 반복적으로 늘어나는 것을 확인한다면 쉽게 풀수있는 문제이다.

 

p[0] = 1

p[1] = 1

p[2] = 1

p[3] = p[0]+p[1] = 2

p[4] = p[1]+p[2] = 2

p[5] = p[2]+p[3] = 3

이런 패턴을 찾게 되었다면

p[n] = p[n-3]+p[n-2] 이라는 것을 알수있다 이를 dp를 통해 풀면 쉽게 문제를 해결할 수 있다.

import sys

input= sys.stdin.readline

dp=[0]*103

dp[0] = 1
dp[1] = 1
dp[2] = 1

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

n = int(input())

for i in range(n):
    temp=int(input())
    print(dp[temp-1])