백준 2156번 "포도주 시식"

문제

백준 2156번 "포도주 시식"

풀이

연속으로 놓여져 있는 세잔을 연속해서 마실 수 없다에 주목해야하는 문제이다.
이 조건으로 3가지 경우를 고려해야 하는것을 알 수있는데

• i-1번째 잔을 마시지 않고 i번째 잔을 마신경우
  arr[i] + dp[i-2]

• i-1번째 잔을 마시고 연속해서 i번째 잔을 마신경우()
  arr[i] + arr[i-1] + dp[i-3]

• i번째 잔을 마시지 않고 넘어가는 경우
  dp[i-1]

이 세가지 조건 중 최대값을 골라 dp배열에 넣고 다음 반복으로 넘어가야 한다.

Python 코드

import sys

input = sys.stdin.readline

n = int(input())
arr = [int(input()) for i in range(n)]
dp=[arr[0]]
if(n>1):
  dp.append(arr[0]+arr[1])

for i in range(2, n):
  # i가 2일 경우 dp[i-3]이 인덱스에서 벗어남 -> dp[i-3]값을 0으로 놓고 연산
  if i == 2:
    dp.append(max(arr[i]+dp[i-2], arr[i]+arr[i-1], dp[i-1]))
  # 이러한 조건문을 쓰고싶지 않을 땐 dp배열 첫 요소에 0을 넣고 인덱스값을 변경하면 된다.
  else:
    dp.append(max(arr[i]+dp[i-2], arr[i]+arr[i-1]+dp[i-3], dp[i-1]))

print(dp[n-1])