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

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

9461번: 파도반 수열

 

 

숫자가 1 1 1 2 2 3 4 5 7 9... 순서로 진행되는데 i-3번째와 i-2번째 숫자를 더해서 i번째 숫자를 만들 수 있다. 점화식을 세우면 dp[i] = dp[i-3] + dp[i-2] 가 된다.

 

import sys
t = int(sys.stdin.readline())
for _ in range(t): #1
    n = int(sys.stdin.readline()) #2
    dp = [0]*(101) #3
    dp[1], dp[2], dp[3] = 1, 1, 1 #4
    for i in range(4, n+1): 
        dp[i] = dp[i-3] + dp[i-2] #5
    print(dp[n])

 

#1 : 테스트 케이스 수만큼 반복

#2 : 숫자입력

#3 : 입력값의 최댓값이 100이니까 101개의 dp리스트 생성

#4 : 점화식을 위해 초기값 3개 생성

#5 : 점화식 입력

 

예시로 주어진 숫자들을 보고 공식을 찾아낼 수 있어야 점화식을 세울 수 있는 문제였다. 비슷한 문제를 더 풀고 dp의 대표유형에 적응하도록 해야겠다.

 

---

1904번 01타일과 비슷한 dp문제