2156번 포도주 시식

 

이 문제는 동적 프로그래밍을 이용한다.

---

문제풀이

이 문제에는 규칙이 있다. 포도주를 전부 마셔야하고, 연속적으로 3잔을 마시지 않아야한다.

따라서 i-1번째 포도주를 마시고 i번째 포도주를 마신 경우 i+1번째 포도주를 마실 수없다.

 

그렇다면 조건을 알 수 있다. 

1. 이번 회차를 포도주를 마실 때, 이전 회차에서 포도주를 마신 경우

2. 이번 회차에 포도주를 마실 때, 이전 회차에서 포도주를 마시지 않은 경우

3. 전회차에서 2연속으로 마셔서 이번 회차에 포도주를 안마실 경우

를 따져봐야한다.

 

입력으로 6,10,13,9,8,1 이 들어올 경우

초기값을 먼저 더한다

초기값을 보자면

연속적으로 더한 값 16

하나 띄우고 더한 값 19

하나 넘기고 연속으로 더한 값 23

 

13을 기준으로 식을 보자

처음의 경우는 wine[i-2] + wine[i-1] 값을 rlt[1]에 저장

두 번째 경우는 wine[i-2] + wine[i] 값을 rlt[2]에 저장

마지막 경우는 wine[i-1] + wine[i] 값을 rlt[3]에 저장한다.

 

이 값을 가지고 위의 식들을 다시 작성해보겠다.

6과 10이 들어왔으면 연속된 값으로 13이 들어오지 못한다.

 

그러므로 9의 값이 들어와야 하기때문에 처음의 식을 다시 작성하자면

처음 경우의 값은 이전 rlt의 값이 최대값이라 가정하고 최대값과 비교한다

 

두번째 식은 지금값과 하나띄우기 전의 결과값을 더하면 현재의 결과값이 나온다.

 

세번째 식은 하나 띄우고 연속적으로 얻은 값이기 때문에 현재 연속적으로 더한 값과

하나 띄우기 전의 값 rlt[-3]을 더해 현재의 최대값을 구할 수 있게 된다.

 

이 세개의 식들의 최대값들을 비교하면 최종적으로 포도주 양의 최대값을 얻을 수 있다.

 

알고리즘은 이런식으로 진행된다.

---

코드

 

import sys
n = int(sys.stdin.readline()); wine = [0]
for _ in range(n):
    wine.append(int(sys.stdin.readline()))
rlt = [0 for _ in range(len(wine))]
for i in range(1, len(wine)):
    if i == 1:
        rlt[1] = wine[1]
    elif i == 2:
        rlt[2] = wine[1] + wine[2]
    else:
        rlt[i] = max(rlt[i-3] + wine[i-1] + wine[i], rlt[i-2] + wine[i], rlt[i-1])
print(rlt[i])