[Python]동적계획법 백준 9461

   문제

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

수를 나열하기 보다는 위 그림을 보면 일정한 규칙을 볼수있다.

P(n-5)와P(n-1)의변이 P(n)의 변을 이루는 모습을 볼수있다.

코드로 짜보자

import sys
 
n=int(sys.stdin.readline())
padoban=[1 for i in range(101)]
padoban[4]=2
padoban[5]=2
for i in range(6,101):
    padoban[i]=padoban[i-1]+padoban[i-5]
 
 
while n>0:
    n-=1
    print(padoban[int(sys.stdin.readline())])