[백준/Python] 9461 파도반 수열

📖  문제 링크

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

9461번: 파도반 수열

 

👩‍💻  문제풀이

생각보다 규칙이 쉽게 찾아진 문제였다!

P(1)부터 P(10)까지 수열을 표로 나열해보니, P(6)부터 규칙적으로 수가 증가하는 것을 확인할 수 있었다.

P(6)의 경우, P(1)과 P(5)의 합이며, P(7)의 경우 P(2)와 P(6)의 합인 것을 확인할 수 있다.

 

즉, 이를 토대로 점화식을 세우면 아래와 같다.

dp[i] = dp[i-5] + dp[i-1]

 

 

dp[1]부터 dp[5]까지는 하드코딩으로 처리해주었다.

 

 

✅  최종 코드

n = int(input())

for _ in range(n):    
    k = int(input())
    dp = [0] * 101
    
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1
    dp[4] = 2
    dp[5] = 2

    for j in range(6, k+1):
        dp[j] = dp[j-5] + dp[j-1]

    print(dp[k])