새싹프로그래머의 이야기

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

문제: 해당 그림과 같이 정삼각형의 변의 길이가 구성될 때, 입력된 N의 값에 따라 파도반 수열에 따른 P(N) 값을 구하는 문제

풀이 방법: 다이나믹 프로그래밍

풀이 설명:

주어진 수열은 다음과 같습니다.

[1,1,1,2,2,3,4,5,7,9]

이 수열을 봤을 때, P(i) = P(i-2) + P(i-3) (i >= 4)인 규칙을 발견할 수 있었습니다.

이를 바탕으로 다이나믹 프로그래밍을 통해 문제를 풀었습니다.

풀이 코드:

import sys

t = int(sys.stdin.readline())

p = [0,1,1,1] + [0] * 97

for _ in range(t):
    n = int(sys.stdin.readline())
    if n > 3:
        for i in range(3,n+1):
            p[i] = p[i-3] + p[i-2]
    print(p[n])