[BOJ] 9461번: 파도반 수 (python)

문제 링크 : https://www.acmicpc.net/problem/9461

💡 해결 방법

• 가운데 삼각형부터 한 변의 길이를 나열해보면 규칙을 찾을 수 있다.
• 규칙은 직전 삼각형과 5번째 전의 삼각형 변의 길이 합이다.
• 따라서 초기 5개의 변의 길이는 먼저 배열에 저장해두고, 이후의 인덱스에 맞게 arr[i] = arr[i-1] + arr[i-5]를 해주면 된다.
• 입력받는 N의 제한이 100이기 때문에 미리 배열을 다 만들어주어도 괜찮았다.
  
  

🖥️ 코드

import sys

T = int(sys.stdin.readline())
arr = [0]*100
arr[0] = 1
arr[1] = 1
arr[2] = 1
arr[3] = 2
arr[4] = 2
for i in range(5, 100):
    arr[i] = arr[i-1]+arr[i-5]

for i in range(T):
    N = int(sys.stdin.readline())
    print(arr[N-1])

✏️ 알고리즘 분류

• 수학
• 다이나믹 프로그래밍