[Python] 파이썬 백준 (9461) 파도반 수열

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

9461번: 파도반 수열

---

나의 풀이

다음과 같이 나선 모양의 삼각형이 있다고 할 때, 가장 긴 변의 길이를 K라고 한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변(k)의 길이이며 N이 주어졌을 때 p(N)을 구하는 프로그램을 작성하자.

---

다음과 같이 인덱스가 있다고 하면 p(n)은 p(n-1) + p(n-5)라고 볼 수 있으며 코드로 나타내면 아래와 같다.

import sys
cnt = int(sys.stdin.readline())
pado = [0]*100
pado[0], pado[1],pado[2],pado[3],pado[4] = 1, 1, 1, 2, 2
for _ in range(cnt):
    n = int(sys.stdin.readline())
    for i in range(5, n):
        pado[i] = pado[i-1] + pado[i-5]
    print(pado[n-1])

---

다른 사람의 풀이

t = int(input())

nList = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
[nList.append(nList[i-3] + nList[i-2]) for i in range(10, 101)]
    
for i in range(t):
    n = int(input())
    print(nList[n-1])

t = int(input())

nList = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
[nList.append(nList[i-1] + nList[i-5]) for i in range(10, 101)]
    
for i in range(t):
    n = int(input())
    print(nList[n-1])

P(n-1) + P(n-5) 말고도 P(n-3) + P(n-2) 규칙도 있으며 그 수식을 넣어서 풀었다.(위아래 둘 다 정답처리)

n이 주어졌을 때 n만큼 연산했던 내 코드와는 다르게 101부터 모든 수를 미리 구하고 n이 들어왔을 때 값을 처리했다.

시간이 오래 걸려서 그리 좋은 코드는 아닌거 같지만 깔끔하니 보기는 좋다.