백준 9461 풀이 (파도반 수열, 메모제이션, 다이나믹 프로그래밍)

이번 문제는 상당히 쉽게 풀었다. 왜냐하면 이전에 피보나치수열을 경험해보았기 때문이다.

파도반 수열은 아래와 같다.

[1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ......]

이 수열의 점화식을 세우면......

f(n) = f(n-1) + f(n-5)

단, n>5이어야한다. 

따라서 제약조건을 토대로 재귀함수를 만들면 피보나치와 거의 유사하다. 하지만 이번에는 메모제이션 기법을 이용하여 효율적인 코딩을 해보기로 한다. (내 머리속 지우개는 굉장히 부지런하다보니 안쓰면 굉장히 빨리 까먹는다. 써볼 수 있을때 많이 써봐야한다.)

n = int(input())

tmp = [0 for i in range(100)]
tmp = [1,1,1,2,2] + tmp

def pado(n):
    if n < 5:
        return tmp[n]
    if tmp[n] == 0: # 없는경우
        tmp[n] = pado(n-1) + pado(n-5)
    else:
        return tmp[n]
    return pado(n-1) + pado(n-5)

for _ in range(n):
    n = int(input())
    print(pado(n-1))

코드의 내용은 아주 간단하다. tmp에다가 0이외에 5이하일경우 반환할 기본적인 값들을 넣어준다.

그리고 인덱스가 5 미만인 경우 해당 값을 바로 반환한다.

만약 인덱스가 5 이상인 경우 배열에 값이 할당되어있는지 확인해보고 값을 반환한다.

 

요렇게 해보니까 바로 문제가 풀렸다.