백준 9416번 파이썬 (python) : 파도반 수열

문제는 이러하고

 

파도반 수열의 규칙을 찾다보니 피보나치 수열이랑 비슷한 느낌의 그림을 볼 수 있었다.

P 는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

그림을 1부터 시작해서 따라가다 보면 알겠지만

6번째 숫자부터 

dp[ i ] = dp [ i - 1 ] + dp[ i - 5 ]

의 점화식이 세워지는 것을 알 수 있다.

import sys

def padovan(n):
    arr=[1,1,1,2,2]
    if n < 6 :
        return arr[n-1]
    for i in range(5,n+1):
        arr.append(arr[i-1]+arr[i-5])
    return str(arr[n-1])

M = int(sys.stdin.readline())
arr = []
for i in range(M):
    arr.append(int(sys.stdin.readline()))

for j in range(M):
    print(padovan(arr[j]))

나는 이런식으로 구현했다.

 

다른 사람들의 코드를 보니

그냥 N을 받지않고 1 <= N <= 100 을 이용해서

그냥 100 까지 구해놓고 

N번째 숫자를 꺼내오는 식으로 간단하게 짠 코드 들이 많았다.

import sys
arr = [0] * 100
arr[0:4] = 1,1,1,2,2
T = int(sys.stdin.readline())

for i in range(5,100):
    arr[i] = arr[i-1] + arr[i-5]

for j in range(0,T):
    N = int(sys.stdin.readline())
    print(arr[N-1])

걸린시간은 동일한데 코드가 훨씬 짧음!