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

import sys
input = sys.stdin.readline

def BOJ2156() :
  n = int(input())
  dp = [[0 for _ in range(3)] for _ in range(n)]
  l = []
  for _ in range(n) :
    l.append(int(input()))
  
  # dp[i][0] = 해당 잔을 마시지 않은 경우
  # dp[i][1] = 앞의 잔을 마시지 않고 해당 잔을 마신 경우
  # dp[i][2] = 앞의 잔을 마시고 해당 잔을 마신 경우

  dp[0] = [0, l[0], l[0]]
  
  for i in range(1, n) :
    dp[i][0] = max(dp[i-1])
    dp[i][1] = dp[i-1][0] + l[i]
    dp[i][2] = dp[i-1][1] + l[i]

  print(max(dp[n-1]))

BOJ2156()

접근 방법 

 

1. 이전까지 포도주를 먹은 총 합이 현재의 선택에 영향을 미치게 된다. 그래서 dp(dynamic programming)을 선택하였다.

2. dp는 현재 포도주 잔에서의 상태에 따라 값을 가지는 배열이다. 

• 포도주를 마시지 않는경우
• 이전의 포도주를 마시지 않고 해당 포도주를 마시는 경우
• 연속해서 포도주를 마시는 경우

3.  포도주를 마시지 않은 경우에는 이전의 선택중 가장 큰 값을 선택하게 한다. 

4. 마지막 포도주를 무조건 마셔야 하는 조건이 없으므로 마지막 까지의 선택중 가장 큰값을 출력해준다.

 

 

 

 

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식