(Python) - BOJ(9461번) : 파도반 수열

https://www.acmicpc.net/problem/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)을 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

그림이 주어져서 쉽게 규칙을 찾을 수 있는 DP 문제이다. 5번째 삼각형 까지는  값을 그대로 입력해주고, 6번째부터 이전 값과 인덱스의 -5 번째에 있는 삼각형의 변을 더해주면 된다.  예를들어, 5번째 삼각형은 4번째의 변 길이인 3과 5-5 즉 0번 인덱스의 값인 1을 더하여 4가 된다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    for _ in range(int(input())):
        ans = [1, 1, 1, 2, 2]
        N = int(input())-1
        start = 5
        if N > 4:
            while start<=N:
                ans.append(ans[-1]+ans[start-5])
                start += 1
        print(ans[N])