[백준/9461] 파도반 수열 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 102
dp[1] = 1
dp[2] = 1
dp[3] = 1

for _ in range(n):
    x = int(input())

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

    print(dp[x])

---

✔ 후기

P(1)부터 P(10)까지 값을 적어놓고 규칙을 찾아가보면 된다.

처음에는 P(5)까지 값을 미리 부여해놔야 하는 줄 알고 P(6)부터 규칙을 찾아봤다.

dp[i] = dp[i-1] + dp[i-2] 인줄 알았으나 P(7)에서 규칙이 맞지 않았다.

결국엔 dp[i] = dp[i-2] + dp[i-3] 규칙을 찾고 P(5)와 P(4)도 같은 규칙이 성립하는 것을 찾아 P(1) ~ P(3) 까지만 초기 값을 부여할 수 있었다.