[백준]9461.파도반수열

문제설명

문제가 간단하여 설명할 것이 없다.

접근 방법

정의를 이해하여 순환식을 작성할 수 있겠지만 복잡해보여서 주어진 수열만으로 규칙을 찾아냈다. 즉, 아이큐 테스트 문제라 생각하고 접근했다.

그래서 규칙을 나타내면 f(n) = f(n-2)+f(n-3)이 되고, n-3을 보듯, 순환식이 적용되는 n의 범위는 n>=4가 된다.

따라서 n= 1, 2 3 일 때 초기값을 정해주었다.

그리고 인풋값의 범위가 최대 100이기 때문에 dp 100번까지 미리 돌고 요청한 값을 출력하면 정답.

그런데 처음에 100을 테스터케이스 최대 수라고 잘못해석하여 범위를 한정지을 수 없다는 생각에 메모제이션으로 푸는 것이 더 간결할 것 같아 메모제이션으로 접근했다.

구현

memo = {1:1,2:1,3:1}

def Wave(n):
    if n in memo:
        return memo[n]
    else:
        memo[n] = Wave(n-2)+Wave(n-3)
        return memo[n]

n = int(input())
for _ in range(n):
    req = int(input())
    print(Wave(req))