백준 9461 파이썬 | 파도반 수열

코드

from sys import stdin

p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12]
for i in range(12, 101):
    p.append(p[i-1] + p[i-5])
T = int(input())
for _ in range(T):
    n = int(input())
    print(p[n])

설명

수열이 어떻게 돌아가는지 한 번 그려 보면 풀기 쉬운 문제이다. 피보나치 수열과 굉장히 비슷한 모양새이다. 피보나치와 비슷해서 동적 프로그래밍으로 문제를 풀었다. 처음 생각할 때는 수열이 좀 더 복잡한 규칙을 가지고 있는게 아닌가 싶은 생각이 들었지만 얼추 수열을 그려보니 그렇지는 않았다. 그림으로 봐도 수열의 규칙을 직관적으로 찾을 수 있다.

 

수열의 i 번째 수는 i-1 번째 수와 i-5 번째 수를 더한 값이다. N의 범위(1-100)를 보고 동적프로그래밍을 이용하여 100까지 수열을 만들어 주었다. 그 다음에는 테스트 케이스 동안 수열의 값을 출력해 주면 된다.

 

아무래도 동적프로그래밍에서는 이런 수열의 형태가 자주 나온다. 문제에 주어진 상황을 잘 보고 직접 하나씩 해 보면 이걸 동적프로그래밍으로 풀어야할지 말아야 할지 판단이 선다.

 

궁금해서 찾아보았더니 파도반이란 사람이 있고 건축가라고 한다. 그의 책에서 이런 수열을 서술하였고 이 수열에 파도반이란 이름을 붙인건 영국의 수학자 이안 스튜와트라고 한다. (https://en.wikipedia.org/wiki/Richard_Padovan)

 

메모리:29200 KB

시간: 84 ms

문제

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

9461번: 파도반 수열