[백준] 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)을 구하는 프로그램을 작성하시오.

풀이1

P(1)부터 P(10)까지 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9로 구성되어있다. 그림에 보이는 대로 규칙을 찾아보면 마지막 숫자와 마지막에서 5번째 숫자가 더해지는 규칙이 있다. 그래서 앞에 1, 1, 1, 2, 2까지 list로 저장을 하고 이후 숫자부터 규칙에 맞춰 코드를 짜봤다.

import sys

t = int(sys.stdin.readline())
p = [0, 1, 1, 1, 2, 2]
for i in range(6, 101):
    result = p[-1] + p[-5]
    p.append(result)
for _ in range(t):
    n = int(sys.stdin.readline())
    print(p[n])

풀이2

다른 풀이를 찾아보니 앞에 1을 3개만 저장을 한후 4번째 숫자부터 n번째 숫자는 (n - 3)번째 숫자 + (n - 2)번째 숫자를 더한 값으로 풀 수 있었다.

p = [0 for i in range(101)]
p[1] = 1
p[2] = 1
p[3] = 1
for i in range(0, 98):
    p[i + 3] = p[i] + p[i + 1]
t = int(input())
for i in range(t):
    n = int(input())
    print(p[n])