백준 9461번 파도반 수열 - Python

문제 링크 : https://www.acmicpc.net/problem/9461

문제를 처음 읽어봤을 땐 이해가 잘 되지 않았다.
먼저 파도반 수열을 통해 나오는 값을 나열해보자.
그럼 규칙을 찾을 수 있다.

1,1,1,2,2,3,4,5,7,9,12,16,21,28,37...

규칙을 보자면, [i] + ([i]+1) = [i]+3 이라는 것을 찾을 수 있다.
인덱스 값으로 계산하면 된다.(헷갈림 주의)

i가 1일 때, 1 + 1 = 2 
i가 2일 때, 1 + 1 = 2
i가 3일 때, 1 + 2 = 3
i가 4일 때, 2 + 2 = 4

풀이

1. 문제에서 주어진 범위는 1~100의 범위이다.
2. index 1,2,3은 1,1,1 이다.
3. 그렇다면 1,2,3은 1로 지정하고 4부터의 범위를 하나씩 돌며 값을 찾아 넣는다.

해답

a = [0 for i in range(101)] # 0부터 100의 범위
a[1] = 1
a[2] = 1
a[3] = 1

for i in range(0,98): # [1,1,1,2,2,3,4,5,7,9,12,16....] 하나씩 돌면서 리스트를 만들어놓음.
    a[i+3] = a[i] + a[i+1]

n = int(input())
for i in range(n):
    m =int(input())
    print(a[m]) # m번째 인덱스 값을 출력해라.