[BOJ/Step15] 9461 : 파도반 수열 (Python)

www.acmicpc.net/problem/9461

9461번: 파도반 수열

---

그림을 보면 점화식을 구할 수 있다

 

보면 순서대로

1 1 1 2 2 3 4 5 7 9 12 … 인데

3부터

3 = 1 + 2 = w(1) + w(5) = w(6)

4 = 1 + 3 = w(2) + w(6) = w(7)

5 = 1 + 4 = w(3) + w(7) = w(8)

7 = 2 + 7 = w(4) + w(8) = w(9)

9 = 2 + 7 = w(5) + w(9) = w(10)

12 = 3 + 9 = w(6) + w(10) = w(11)

인 걸 알 수 있다

결국 w(n) = w(n-1) + w(n-5)

 

근데 또 t를 받고 t번 반복해야 하기 때문에

입력값 n이 미리 배열에 넣어둔 수를 넘어가면 매번 새로 구해야 하는 번거로움이 있기 때문에

이전에 입력받은 n보다 작은 수를 입력받으면 바로 출력할 수 있도록 조건문을 추가한다

 

1. n을 입력받는다

2. n이 wave의 길이 -1보다 작거나 같으면 wave[n]을 바로 출력한다

3. for문을 통해 wave[len(wave) = l]부터 wave[n]까지 추가한다

4. wave[n]을 출력한다

 

# 9461.py

t = int(input())
wave = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

for i in range(t):
    n = int(input())
    if n <= len(wave) - 1:
        print(wave[n])
    else:
        for l in range(len(wave), n+1):
            wave.append(wave[l-1] + wave[l-5])
        print(wave[n])