[다이나믹 프로그래밍] 2156번 - 포도주 시식

[백준] 2156번 - 포도주 시식

(한줄평) 점점 dp문제 감을 찾는 것 같다고 느껴진 문제!

유사 문제: 2579

https://hseungyeon.tistory.com/300

[다이나믹 프로그래밍] ▲ 2579번 - 계단 오르기

풀이 시간: 10분 이내

1) 문제 해결 아이디어

2가지 조건을 만족하며 n개의 포도주 중 최대로 마실 수 있는 포도주의 양을 구하는 문제다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

2579번 문제와 거의 유사한 문제다. 다만 다른 점이 있다면 2579번 같은 경우에는 무조건 마지막 계단은 선택해야한다는 조건이 있기 때문에 점화식을 세울 때 마지막 끝값은 무조건 선택한다고 가정하고 경우의 수를 계산했다. 하지만 이 문제는 마지막을 무조건 선택해야한다는 조건이 없기때문에 마지막 포도주는 선택할 경우, 선택하지 않을 경우를 모두 고려해야한다는 것이 중요 포인트다!

 

<경우의 수>

마지막 잔을 선택한 경우는 2가지로 또 나눠지고 마지막 잔을 선택하지 않은 경우는 1가지이다. 

1. ~ XOO일 때

- i가 O, (i-1)이 O이면 (i -2)는 무조건 X여야한다. 조건2에서 연속으로 놓여 있는 3잔을 모두 마실 수는 없다했기 떄문이다.

2. ~ XO일 때

- i가 O, (i-1)이 X이면 (i-2)는 O, X 둘 중 아무거나 와도 상관이 없다.

3. ~ X일 때

- i가 X이면 (i - 1)은 O, X 둘 중 아무거나 와도 상관이 없다.

 

<점화식>

2) 소스코드

import sys
input = sys.stdin.readline

n = int(input())  # 포도주 잔의 개수(1이상 10000이하)
graph = [int(input()) for _ in range(n)]  # n개의 포도주 양

if n == 1:
  print(graph[0])
else:
  d = [0] * n  # i번째까지 마실 수 있는 포도주의 최대양
  d[0] = graph[0]
  d[1] = graph[0] + graph[1]
  for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + graph[i], d[i - 3] + graph[i-1] + graph[i])
  print(d[n - 1])