[백준]9461번 파도반 수열 - DP

 

n = int(input())

length = []
for i in range(n):
    case = int(input())

    tri = [1, 1, 1]
    if case >= 3:
        for i in range(3, case):
            tri.append(tri[i - 3] + tri[i - 2])

    print(tri[-1])

 

코드 설명

3번째까지의 초기 값을 tri 리스트에 저장하여 준다. 3이상의 경우가 나올때는 점화식을 이용해 값을 구해준다.

1 -> 1 -> 1 -> 2-> 2 -> 3 -> 4 -> 5 -> 7 -> 9 -> 12 -> 16 과 같은 형태로 계속 늘어난다.

유심히 살펴보면 i 번째의 길이는 i-3 + i-2 의 값임을 유추할 수 있다. 이를 활용해 점화식을 세울 수 있다.

 

Point : 수가 증가하는 규칙을 살펴보고 i 번째의 값은 i-3 + i-2 의 값이 되는 것을 알 수 있었다.