[Baekjoon] 9461번 : 파도반 수열 (Python)

[Baekjoon] 9461번 : 파도반 수열 (Python)

 

목차

 

 

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

Python

 

방법 1 - 메모리 30860 / 시간 84ms / 코드 길이 144B

삼각형의 변의 길이를 나열하면 다음과 같습니다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37 ...

 

수를 잘 보면 특정 점화식이 보이는데 저는 크게 2개로 보여졌습니다.

1) N번째의 숫자는 N-1 숫자 + N-5 숫자를 더한 값 

2) N번째의 숫자는 N-2 숫자 + N-3 숫자를 더한 값 

 

이를 기반으로 memorization을 진행하면 되는 문제입니다.

 

l = [0,1,1,1,2,2] + [0]*96
for i in range(6,101):
    l[i] = l[i-1] + l[i-5]
    #l[i] = l[i-2] + l[i-3]

for i in range(int(input())):
    t = int(input())
    print(l[t])

 

참고)

import sys

input = sys.stdin.readline

을 추가로 넣으면 시간이 72ms로 줄어듭니다.