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

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

 

 

사용 알고리즘: DP

 

 

입력

첫째 줄에 테스트 케이스의 개수 T

N (1 ≤ N ≤ 100)

 

 

첫 삼각형은 정삼각형으로 변의 길이는 1

다음과 같은 과정으로 정삼각형을 계속해서 추가할 때 나선에서 가장 긴 변의 길이 찾기

 

 

이 문제는 그림을 보고 규칙을 찾아서 쉽게 풀 수 있었다.

 

P(1) = 1

P(2) = 1

P(3) = 1

P(4) = 2

P(5) = 2

P(6) = P(5) + P(1)

P(7) = P(6) + P(2)

P(8) = P(7) + P(3)

P(9) = P(8) + P(4)

P(10) = P(9) + P(5)

 

점화식을 써보면

-> P(n) = P(n-1) + P(n-5)

 

 

인덱스 1부터 사용할거라 0번 인덱스에는 0을, 1~5번 인덱스에는 해당 값을 미리 넣었다. 

5번까지의 인덱스에는 이미 값이 있기 때문에 N 값이 5 이하라면 첫번째 if 문에서 처리되고, 6 이상의 값들은 for 문을 돌면서 처리된다.

def dp(N):
    dp = [0, 1, 1, 1, 2, 2]
    
    if N <= 5:
        return dp[N]
    for j in range(6, N+1):
        dp.append(dp[j-1] + dp[j-5])
    return dp[N]

 

 

전체코드

import sys
input = sys.stdin.readline

# P(N)값을 계산해줄 함수
def dp(N):

    dp = [0, 1, 1, 1, 2, 2]
    
    # 5 이하
    if N <= 5:
        return dp[N]
    # 5 초과
    for j in range(6, N+1):
        dp.append(dp[j-1] + dp[j-5])
    return dp[N]

# 입력
T = int(input())
N = [int(input()) for __ in range(T)]

for i in range(T):
    print(dp(N[i]))