[Python] 백준 9461번:파도반 수열 / 문제 풀이, 설명

[Python] 백준 9461번:파도반 수열 / 문제 풀이, 설명

---

º 코드

def Dp(n):
    tri = [1,1,1]
    if n>=4:
        for i in range(3,n+1):
            tri.append(tri[i-2] + tri[i-3])
    return tri[n-1]

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

• n은 1부터 시작하니 tri 인덱스와 맞추기 위해 -1을 해야한다.

---

º 풀이 과정

1. ( 1,1,1,2,2,3,4,5,7,9 - - - ) 이렇게 숫자가 늘어선다
2. 수의 규칙을 잘 보면 4번째부터 f(4) = f(2)+f(1) / f(5) = f(3) + f(2) / f(6) = f(4) + f(3) 이렇게 된다. 결국 N이 4이상 일 때    f(N) = f(N-2) + f(N-3) 이 된다.