백준 9461번 Python / Dynamic Programming

문제 링크

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

9461번: 파도반 수열

 

풀이

T = int(input())
arr = [0] * 101
arr[0] = 1
arr[1] = 1
arr[2] = 1

for i in range(0,98):
    arr[i+3] = arr[i] + arr[i+1]

for _ in range(T):
    n = int(input())
    print(arr[n-1])

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

규칙을 보면 i+3 번째의 수가 i 번째와 i+1 번째의 합인 규칙을 발견할 수 있습니다.

따라서, 해당 규칙으로 100개의 수를 리스트에 만들어 저장한 후,

입력을 받아 출력만 해주면 끝입니다!

처음에 arr리스트에 0을 101개 채운 이유는 for문에서 0~98 범위에서 +3번째까지 지정하기 때문에 100으로 하면 range오류가 발생합니다.