[파이썬/백준 9461번] 파도반 수열

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

이제 좀 동적계획법이 뭔지 익숙해 진 것 같다.

점화식을 알아내는게 동적계획법의 핵심인듯

 

처음 12개정도는 하나씩 보면서 규칙을 찾았다.

5번째부터는 바로 전 숫자와 5번째 전 숫자의 합이라는것을 알아내어 점화식을 썼고,

첫 5번째까지는 별다른 규칙이 없어서 임의로 입력해서 사용했다.

 

def P(n):
    if n<=5 : return arr[n]
    if arr[n]: return arr[n]
    arr[n]=P(n-1)+P(n-5)
    return arr[n]

N=int(input())
arr=[0 for _ in range(101)]
arr[:5]=[0,1,1,1,2,2]
for i in range(N):
    print(P(int(input())))

함수를 따로 쓰는게 습관인가,,

 

함수 없이 해도 잘 됨

N=int(input())
arr=[0 for _ in range(101)]
arr[:5]=[0,1,1,1,2,2]
for i in range(N):
    a=int(input())
    for j in range(6,a+1):
        arr[j]=arr[j-1]+arr[j-5]
    print(arr[a])

심지어 속도도 조금 더 빠름..