boj9461 파도반 수열

제목 : 파도반 수열(boj 9461번)
난이도 : silver 3🥈
관련 알고리즘 : DP

1. 알고리즘 설명

파도반 수열의 규칙만 잘 찾는다면 피보나치 수열과 같은 방법으로 풀면 됩니다.

파도반 수열은 두 칸 앞의 수 와 세 칸 앞의 수 의 합으로 정리할 수 있습니다.

\(F_n = \cases{ 0 & \text{if } n = 0\cr 1 & \text{if } n\le 2\cr F_{n-2} + F_{n-3} & \text{if } n\gt 2 }\)

2. python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 메모리 : 122244 KB
# 시간 : 116 ms

memo = [0, 1, 1]

def dp(n):
    for _ in range(n-2):
        memo.append(memo[-2] + memo[-3])
    
    return memo[n]

T = int(input())
for _ in range(T):
    N = int(input())
    print(dp(N))

잘못된 내용이 있거나 조언이 있다면 언제든지 환영입니다^.^