[백준][Python] 9461. 파도반 수열

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

 

출력

각 테스트 케이스마다 P(N)을 출력한다.

---

코드

import sys

if __name__ == '__main__':
    list = [1,1,1]

    T = int(sys.stdin.readline().rstrip())
    pn = []
    for i in range(T):
        pn.append(int(sys.stdin.readline().rstrip()))
    
    maximum = max(pn)

    for i in range(3, maximum):
        list.append(list[i-2] + list[i-3])
  
    for i in range(T):
        print(list[pn[i]-1])

 

풀이

10개의 P(N)이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 라는 것을 주목하면, 뭔가 피보나치와 닮아있다는 것을 느낄 수 있을 것이다. 첫 번째 수 + 두 번째 수 = 2, 두 번째 수 + 세 번째 수 = 2, 세 번째 수 + 네 번째 수 = 3 이걸 나열하면 223이다. 즉 예시에 있는 것과 겹치는 부분이 있다는 것을 확인할 수 있다. 세 번째 수와 네 번째 수를 더해서 여섯 번째 수가 나온 것을 보면, 현재 수는 앞 앞 번째 수와 앞 앞 앞 번째 수를 더한 것임을 알 수 있다.

N을 입력 받을 때마다 첫 번째부터 원하는 N번째까지 P(N)을 계속 구하면 시간이 오래 걸릴 것 같아서 입력받은 N 중에서 최댓값을 알아내고, 그 최댓값까지 P(N)을 구해놓았다. 그 후 입력받은 N에 따른 P(N)을 출력했다.