[ BOJ 9461 ] 파도반 수열(Python)

문제

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

p(n)은 나선에 있는 정삼각형의 변의 길이다.

문제 풀이

그림을 그리면 쉽게 풀 수 있다.

약간 지저분하지만,, 어떤 걸 더해야 다음 항을 구할 수 있는지 직관적으로 확인할 수 있다.

dp[i] = dp[i-3] + dp[i-2]

코드

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    dp = [0] * (101)

    dp[1], dp[2], dp[3] = 1, 1, 1
    for i in range(4,n+1):
        dp[i] = dp[i-3] + dp[i-2]

    print(dp[n])