백준 9461 파이썬 - 파도반 수열 - 동적 계획법

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

9461번: 파도반 수열

피보나치와 비슷하게 규칙이 있는 파도반 수열의 N번째 값을 구하는 알고리즘 문제입니다. 위의 그림을 보면 알 수 있듯이... 정삼각형의 변을 따라 계속 늘려가는데... 정삼각형의 변의 길이가 수열의 값으로 들어간다.

 

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16...

가장 핵심은 파도반 수열의 규칙을 찾는 것이었습니다. 

위의 규칙을 기반으로 하고 있습니다. 근데 조건으로 n이 8보다 크다고 적은 이유는 실제로 사용하는 삼각형을 기준으로 한 것이고... n이 5보다 크다는 조건은 해당 수열의 첫 3 숫자가 모두 1이기 때문에 8에서 3을 뺀 식 입니다.

 

 

Python 풀이 1

n > 8으로 가정한 풀이 입니다.

import sys
read = sys.stdin.readline

cache = [0, 1, 1, 1, 2, 2, 3, 4, 5] + [0 for _ in range(100)]

for i in range(9, 101):
    cache[i] = cache[i-1] + cache[i-5]

for _ in range(int(read())):
    print(cache[int(read())])

• 미리 초기값을 8번째 요소까지 지정해주고 최대 100까지 찾는 알고리즘이기 때문에 여유 있게 미리 리스트를 0으로 채워줬습니다.

 

Python 풀이 2

n > 5으로 가정한 풀이 입니다.

import sys
read = sys.stdin.readline

cache = [0, 1, 1, 1, 2, 2] + [0 for _ in range(100)]

for i in range(6, 101):
    cache[i] = cache[i-1] + cache[i-5]

for _ in range(int(read())):
    print(cache[int(read())])

풀이 1과 크게 다르지 않습니다. 단, 초기값을 줄이고 계산을 시작하는 범위를 앞당겼을 뿐입니다.