2156 포도주 시식

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

✔ 유형 : DP

✔ 문제 풀이: 

위의 규칙을 따라서 마실 포도주를 선택해야한다.

점화식을 세우는 접근방식은 다음과 같다

 

1. 맨 마지막 포도주를 무조건 선택한다 했을 때, 연속 두개를 선택하고 싶다면, 

arr[i] ( 마지막 포도주 ) , arr[i-1]( 마지막에서 두번째 포도주), 그리고 3개를 연속해서 선택할 수 없으므로

arr[i-2]는 선택하지 않는다.

 

2. 맨 마지막 포도주를 무조건 선택하고, 그 전 포도주는 선택하지 않을 때,

arr[i] ( 마지막 포도주 )를 선택하고, arr[i-1]는 선택하지 않는다.

 

3. 맨 마지막 포도주를 절대 선택하지 않을 때

DP[i-1]  포도주의 개수가 N-1때의 최대값을 반영하면 된다.

 

이를 일반화 하면

DP[i]는 세가지의 경우의 수로 일반화 하여 식을 세울 수 있다.

DP[i] = arr[i] + arr[i-1] + DP[i-3]

DP[i] = arr[i] + DP[i-2]

DP[i] = DP[i-1]

 

마실 수 있는 최대 포도주의 값을 구해야 하므로 세가지 경우의 수의 값 중 가장 큰 값을 반영하면 된다.

 

따라서,

DP[i] = max( arr[i] + arr[i-1] + DP[i-3] , rr[i] + DP[i-2] , DP[i-1] )로 점화식을 세울 수 있다.

 

코드

import sys
input = sys.stdin.readline

N = int(input())

arr = [ 0 for _ in range(N+1)] # arr도 1부터 시작

for _ in range(1,N+1):
    arr[_] = int(input())

DP = [ 0 for _ in range(N+1)]
DP[1] = arr[1]

# 초기값 예외처리
if N >= 2:
    DP[2] = DP[1] + arr[2] 

if N >= 3:
    for i in range(3, N+1):
        DP[i] = max(DP[i-1],DP[i-2] + arr[i] , DP[i-3] + arr[i] + arr[i-1])
        
print(DP[N])

 

 

이번 문제는 silver3 문제인 계단 오르기문제와 비슷하다고 느꼈는데, 아래 문제도 함께 생각해보면 좋을 것 같다.

2579 계단 오르기