https://www.acmicpc.net/problem/2156
알고리즘 분류
- 다이나믹프로그래밍
문제풀이
백준 2579 계단오르기 문제와 상당히 유사하다.
차이점은 계단오르기는 마지막 계단을 꼭 밟고 끝나지만, 이 문제는 마지막 잔을 마시지 않을 수도 있다는 것이다.
d[i]는 i번째 포도주까지 최대로 마신 포도주의 양이다.(0부터)
i번째 포도주를 마시고 i-2번째까지 마신 양, i,i-1번째를 포도주를 마시고 i-3번째까지 마신 양, 그리고 i번째를 마시지 않는 경우(i-1번째 포도주까지 마신 양)를 모두 고려해야한다.
따라서 결과리스트는 [6, 16, 23, 28, 33, 32..]가 아니라 [6, 16, 23, 28, 33, 33..]이어야 한다.
어떤 한 분이 설명을 되게 잘해주셨다.
->https://www.acmicpc.net/board/view/60664
소스코드
n=int(input())
array=[0]*10000
for i in range(n):
array[i]=int(input())
d=[0]*10000
d[0]=array[0]
d[1]=array[0]+array[1]
d[2]=max(array[2]+array[0], array[2]+array[1], d[1])
for i in range(3,n):
d[i]=max(array[i]+d[i-2], array[i]+array[i-1]+d[i-3], d[i-1])
print(max(d))