[백준 9461] 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

---

접근

변의 길이가 증가하는 규칙을 찾아보면 현재 i번째 길이를 구한다고 했을 때 (i-2) + (i-3)을 통해 구한다.

따라서 위의 점화식을 토대로 구현하도록 한다.

 

구현

초기 세 개의 길이를 1로 초기화하고 이후의 길이는 i = (i-2) + (i-3)이라는 점화식을 통해 구하도록 한다.

test_case = int(input())
for tc in range(test_case):
    N = int(input())
    # 최대 N이 100이기 때문에 100칸 짜리 리스트를 0으로 초기화
    numbers = [0 for _ in range(100)]
    
    # 초기 세 개의 길이는 1이다.
    numbers[0] = 1
    numbers[1] = 1
    numbers[2] = 1
    if N <= 3:
        answer = numbers[N-1]
    else:
        for idx in range(3, N):
            numbers[idx] = numbers[idx-2] + numbers[idx-3]
        answer = numbers[N-1]
    print(answer)