<문제>
<입출력>
<풀이>
1. 계단이 1, 2개 일때는 모두 더한 값이 최대 값이다.
2. 계단이 3개 이상일 때는 현재 계단을 k (k>=3)번 이라 할때, (price[k] + price[k-2])와 price[k] + price[k-1] + price[k-3]) 의 값을 비교하여 최댓값을 저장해주어야 한다.
<코드>
n = int(input())
s = [int(input()) for _ in range(n)] # 각 계단의 점수 리스트
max_score = [0] * (n)
if len(s) <= 2: # 계단이 1,2개일 때는 총합
print(sum(s))
else: # 계단이 3개 이상일 때
max_score[0] = s[0] # 첫번째 계단
max_score[1] = s[0] + s[1] # 두번째 계단
for i in range(2, n): # 세번째 계단부터 비교해서 최대값 저장
max_score[i] = max(max_score[i - 3] + s[i - 1] + s[i], max_score[i - 2] + s[i])
print(max_score[n-1])
<결과>
'코딩 테스트 > 다이나믹 프로그래밍' 카테고리의 다른 글
[백준 11722번] 가장 긴 감소하는 부분 수열 문제 풀이 with Python (0) | 2023.08.22 |
---|---|
[백준 11049번] 행렬 곱셈 순서 문제 풀이 (0) | 2023.08.21 |
[백준 15486번] 동전 1 문제풀이 (0) | 2023.08.01 |
[백준 15486번] 퇴사 2 문제풀이 (0) | 2023.07.31 |
다이나믹 프로그래밍 개념 (0) | 2023.07.23 |
댓글