[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])