백준 9461번: 파도반 수열 python

https://www.acmicpc.net/problem/9461

문제 이해

나선형의 모양으로 삼각형이 계속 추가된다고 한다.

1 1 1 2 2 3 4 5 7 9 가 주어졌는데 보니

f(1) = 1
f(2) = 1
f(3) = 1
f(4) = 2
f(5) = 2
f(6) = 3
f(7) = 4
f(8) = 5
f(9) = 7
f(10) = 9

f(n) = f(n-2) + f(n-3) 의 식이 유추된다.

코드 및 풀이

import sys 

input = sys.stdin.readline

# 테스트 케이스 개수
T = int(input())

# 파도반 수열의 최대 범위 (100까지 계산해두면 충분)
MAX = 101
dp = [0] * MAX

# 초기값 설정
dp[1] = dp[2] = dp[3] = 1

# 점화식을 이용해 미리 계산해둔다
for i in range(4, MAX):
    dp[i] = dp[i - 2] + dp[i - 3]

# 테스트 케이스에 대해 결과 출력
for _ in range(T):
    N = int(input())
    print(dp[N])