[Python] 백준 9461번. 신나는 함수 실행

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

9461번: 파도반 수열

문제설명:

삼각형이 나선 모양으로 놓여져 있을때 첫 삼각형은 정삼각형으로 변의 길이가 1이다. 그 다음 규칙에 맞게 계속 정삼각형이 추가된다.

n이 주어졌을 때, P(N)을 구하는 프로그램이다.

 

문제설계:

이미 문제에서 수열이라고 알려주고 있다. 하지만 다시 생각해보자

삼각형을 나선형으로 만들어지고 있다.

2가 되었을때 1+1로 밑변으로 2가 만들어지고 있다.

3은 밑변 1+2로 만들어지고 있다.

4는 밑변 3+1로 만들어지고 있다.

..(생략)

[1,1,1,2,2,3,4,5,7,9]

lst[4] 2는 1+1 / lst[5] 2는 1+1

lst[6] 3은 1+2 / lst[7] 4는 2+2

..(생략)

9다음으로 올 숫자는 5+7 = 12가 된다.

12다음으로 올 숫자는 7+9 = 16이 된다.

다음에 올 숫자는 그 전전 숫자와 전 숫자의 합 수열이다.

 

• [1,1,1] 이후부터 전전 숫자와 전 숫자의 합이 그 다음 숫자가 된다.
• n을 입력받았을때 인덱스의 기준은 전전숫자의 인덱스에 맞춘다.
• 만약 리스트의 길이가 n보다 크거나 같다면 이미 n 인덱스에 맞는 숫자가 들어있다는 것
• 작으면 수열을 진행한다.

 

import sys

input = sys.stdin.readline

T = int(input())
lst = [1,1,1]
i = 0
for case in range(T):
    n = int(input())
    # n을 입력받았을때 인덱스의 기준은 전전숫자의 인덱스에 맞춘다.
    i = len(lst)-3
    while True:
    	# 리스트의 길이가 n보다 크거나 같다면 이미 n 인덱스에 맞는 숫자가 들어있다는 것
        if len(lst) >= n:
            print(lst[n-1])
            break
        lst.append(lst[i]+lst[i+1])
        i += 1