[백준/파이썬] 2156 포도주 시식

bye9·2021년 2월 4일
1

알고리즘(코테)

목록 보기
52/130

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))

0개의 댓글