카테고리 없음
[BOJ] 9461 / 파도반 수열 / Python 파이썬
migrationArc
2021. 5. 16. 20:53
[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])