공부 기록장
[백준 - Python] 9461. 파도반 수열 (DP) 본문
https://www.acmicpc.net/problem/9461
코드
T = int(input())
for _ in range(T):
N = int(input())
dp = [0] * (N+1)
for i in range(1, N+1):
if i == 1 or i == 2 or i == 3:
dp[i] = 1
elif i == 4 or i == 5:
dp[i] = 2
elif i == 6:
dp[i] = 3
elif i == 7:
dp[i] = 4
elif i == 8:
dp[i] = 5
else:
dp[i] = dp[i-1] + dp[i-5]
print(dp[N])
처음 정삼각형부터 이어서 붙는 삼각형들을 눈으로 따라가보면서
어떤 규칙이 있을까 생각을 해보았다.
정삼각형이 시계방향으로 돌면서 나선 형태로 이어 붙는데
변의 길이가 5인 정삼각형부터는
첫번째 정삼각형(1)과 마지막 정삼각형(4)의 두 변의 길이를
합친 길이만큼의 정삼각형이 붙는 것을 확인할 수 있다.
따라서 dp[i] = dp[i-1] + dp[i-5] 이라는 점화식을 도출할 수 있었다.
'코딩 테스트 > 백준 문제 풀이' 카테고리의 다른 글
[백준 - Python] 11053. 가장 긴 증가하는 부분 수열 (DP) (0) | 2024.02.15 |
---|---|
[백준 - Python] 2193. 이친수 (DP) (0) | 2024.02.15 |
[백준 - Python] 11726. 2xn 타일링 (DP) (0) | 2024.02.10 |
[백준 - Python] 1003. 피보나치 함수 (DP) (0) | 2024.02.10 |
[백준 - Python] 9095. 1, 2, 3 더하기 (DP) (0) | 2024.02.10 |