[파이썬/Python] 백준 9461번 파도반 수열

[파이썬/Python] 백준 9461번 파도반 수열

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)을 출력한다.

예제 입력

2
6
12

예제 출력

3
16

풀이

import sys
input = sys.stdin.readline

# 파도반 수열을 저장할 리스트 초기화
P = [1, 1, 1, 2, 2]

# 나선에 정삼각형을 추가하는 과정을 통해 파도반 수열 생성
for _ in range(95):
    P.append(P[-1] + P[-5])

# 테스트 케이스의 개수 입력
T = int(input())

# 각 테스트 케이스에 대해 파도반 수열의 값을 출력
for _ in range(T):
    # 정수 N 입력
    N = int(input())
    
    # 결과 출력
    print(P[N-1])

 

이 문제는 동적 프로그래밍(Dynamic Programming)의 일종으로, 작은 부분 문제를 풀고 그 해답을 활용하여 전체 문제의 해답을 구하는 방식을 사용하고 있다. 미리 계산된 값을 활용하여 중복 계산을 피하면서 효율적으로 문제를 해결하고 있다.

 

해당 코드는 주어진 문제에서 파도반 수열의 규칙을 활용하여 효율적으로 결과를 도출하는 프로그램이다. 파도반 수열은 나선에 정삼각형을 추가하는데, 가장 긴 변의 길이를 기준으로 정삼각형을 추가한다. 미리 95개까지의 값을 계산하여 리스트 P에 저장한 후, 각 테스트 케이스에서 입력된 N에 해당하는 값을 출력한다.

주어진 문제에서는 이미 최대 100까지의 값을 미리 계산하여 저장해둔 상태이다. 따라서 각 테스트 케이스에 대해 단순히 저장된 값을 출력하므로 시간 복잡도는 O(1)이다. 미리 계산된 값들을 활용하여 중복 계산을 피하고 있어 실행 시간이 매우 짧다.