[백준 BOJ_9461] 파도반 수열 Python 풀이

출처: 백준 온라인 저지

문제

풀이

파도반 수열이라 해서 피보나치 수열과 크게 다를 바가 없습니다.

피보나치 수열은 fib(N) = (N-1) + (N-2) 이라면, 파도반 수열은 (N-2) + (N-3) 입니다.

동적계획법으로 간단하게 cache[0], cache[1], cache[2]까지 각각 0, 1, 1로 초기화 해준 뒤 피보나치 수열을 구할 때와 숫자만 다르게 구해줍니다.

코드

def pado(n):
    if cache[n] == -1:
        cache[n] = pado(n-2) + pado(n-3)
    return cache[n]
T = int(input())
for _ in range(T):
    N = int(input())
    cache = [-1 for _ in range(101)]
    cache[0] = 0
    cache[1] = 1
    cache[2] = 1
    print(pado(N))