몽상실현개발주의

[BOJ] 9461 / 파도반 수열 / Python 파이썬 본문

카테고리 없음

[BOJ] 9461 / 파도반 수열 / Python 파이썬

migrationArc 2021. 5. 16. 20:53

[BOJ] 9461 / 파도반 수열 / Python 파이썬

[BOJ] 9461 / 파도반 수열 / Python 파이썬

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

 

9461번: 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의

www.acmicpc.net

풀이

기본적인 점화식 풀이 문제 이다.

 

파도반 수열

N = 1 -> 1
N = 2 -> 1
N = 3 -> 1
N = 4 -> 2
N = 5 -> 2
N = 6 -> 3
N = 7 -> 4
N = 8 -> 5
N = 9 -> 7

 

 

점화식은 N > 5 일때 부터 적용 된다.

 

dp(N) = dp(N-1) + dp(N-5) (N > 5)

 

 

T = int(input())

for _ in range(T):
    N = int(input())
    
    dp = [0] * 101
    
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1
    dp[4] = 2
    dp[5] = 2
    
    for i in range(6, N+1):
        dp[i] = dp[i-1] + dp[i-5]
        
    print(dp[N])

 

Comments