백준 9461 - 파도반 수열

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

9461번: 파도반 수열

import sys

input = sys.stdin.readline

n = int(input())
arr = [0]*101
arr[1] = 1
arr[2] = 1
arr[3] = 1
for i in range(4,101):
    arr[i] = arr[i-3]+arr[i-2]
for i in range(n):
    print(arr[int(input().strip())])

문제만 보면 어려워 보이긴 한데, 수열 사이에 규칙이 있다.

1,1,1,2,2,3,4,5,7,9....

n번째 값은 n-3번째 값과 n-2번째 값의 합이 된다.

첫 2 = 첫 1+두번째 1

두번째 2 = 두번쨰 1+세번째 1

3 = 세번째 1 + 첫 2

4 = 첫 2 + 두번째 2

....

그러므로 dp로 미리 값들을 싹 다 계산해서 arr에 넣어 둔 뒤 입력값 번호에 해당하는 arr을 넣어 주면 된다.

 

위 코드에서 arr[0]은 고려하지 않으므로 arr[i]는 i번째 삼각형의 변의 길이가 될 수 있다.