백준 9461번 바로가기

나의 풀이

# 입력
import sys
read = sys.stdin.readline
arr = [1,1,1,2,2] + [0]*100

# 처리
for i in range(99):
  arr[i+5] = arr[i+4] + arr[i]
for _ in range(int(read().strip())):
  print(arr[int(read().strip())-1])

CODE REVIEW

  1. 규칙이 잘 안보이길래 n이 1부터 12일 때까지 P(N)값을 구해놓고 규칙을 찾아보았다.
  2. 점화식으로 $a_{n+5} = a_{n+4} + a_{n}$ 과 같다.
  3. 여러 번 불러와야 하므로 105개 정도의 요소를 가진 arr을 미리 구해놓는게 빠르다.