baekjoon(9461-파도반 수열)_python

1) 문제

2) 예시

 

3) 제출

# 첫 번째 제출한 코드

import sys
input = sys.stdin.readline

padovan = []
def padovan(n):
    if n <= 3:
        return 1
    elif n <= 5:
        return 2
    elif n <= 8:
        return n - 3
    elif n == 9:
        return 7
    elif n == 10:
        return 9
    else:
        return padovan(n - 1) + padovan(n-5)

result = list()

for i in range(0, int(input())):
    result.append(padovan(int(input())))

print(*result, sep="\n")

#두 번째 제출한 코드

import sys
input = sys.stdin.readline

question = []

for i in range(0, int(input())):
    question.append(int(input()))

padovan = [0] * (max(question) + 1)

padovan[1], padovan[2], padovan[3] = 1, 1, 1
padovan[4], padovan[5] = 2, 2
padovan[6], padovan[7], padovan[8] = 3, 4, 5
padovan[9] = 7
padovan[10] = 9

for i in range(11, max(question) + 1):
    padovan[i] = padovan[i - 1] + padovan[i - 5]

for i in question:
    print(padovan[i])

4) 메모리/시간/코드 길이

5) PLUS

함수에 그때마다 호출하는 방법을 사용했는데 시간 초과가 떴다.

전에 dp 문제로 피보나치수열을 풀었을 때도 저런 코드로 했더니 시간 초과가 나서 두 번째 코드처럼 리스트에 넣고 계산하는 시간을 줄였다.

이번에도 비슷하게 리스트에 넣고 계산하는 시간을 줄이고 전에 넣었던 리스트에서 호출하기만 하면 돼서 시간이 줄게 된다.

 

파도반 함수는 사실 잘 몰라서 구글링해 수열의 규칙을 찾았다.