문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

예제 입력
6
6
10
13
9
8
1

예제 출력
33

접근방법

동적계획법을 활용한 기본적인 문제풀이법은 다음과 같다.

1. 문제를 분석해서 부문제로 분할한다.
2. 부문제의 해를 이용하여 큰 문제의 해를 표현한다(점화식 세우기).
3. 세운 점화식을 이용해 표를 채운다.
4. 알고리즘의 정확성을 확인하며 표에서 최종해를 구한다.

동적계획법이란 규칙성을 파악하는 것이 핵심이다. 직관이 뛰어나거나 DP 문제에 익숙한 사람들은 단번에 점화식을 세우기도 하지만, 대다수의 사람들에겐 쉽지 않을 것이다. 게다가, 점화식 문제를 분석해서 부문제로 분할하는 것 자체가 잘 안되는 경우도 있다. 그럴 땐 역으로 주어진 예제나 반례들을 이용하여 표를 먼저 채워보는 것도 해결법이 될 수도 있다.

떠올린 생각들

1. 해를 구할 때 연속 2번이 허용되지 않는 문제를 생각해봤다.

이때, DP[i]를 구하는 데에 있어 DP[i-1], DP[i-2]가 부분해가 된다.
그렇다면, 연속 3번이 허용되지 않는 문제에선 DP[i-1], DP[i-2], DP[i-3]이 부분해가 되지 않을까?

2. 계단 오르기 문제처럼 연속 3칸이 되는 상황을 피하는 점화식을 세운다.

연속 3번을 피하기 위해선, 최소 1칸의 공백을 만드는 점화식을 세운다.
다만, 계단 오르기와 달리 비연속적인 선택이 가능함을 주의한다.
DP[i] = max(DP[i-3]+W[i-1]+W[i], DP[i-2]+W[i], DP[i-1])
계단 오르기(2579번) https://www.acmicpc.net/problem/2579

코드

import sys
from collections import deque

n = int(sys.stdin.readline().strip())
W = deque([int(sys.stdin.readline().strip()) for _ in range(n)])
for _ in range(3): 
    W.appendleft(0)  #  더미 데이터를 삽입 
DP = [0] * (n+3)  # 더미 데이터를 삽입

for i in range(3, n+3):
    DP[i] = max(DP[i-3]+W[i-1]+W[i], DP[i-2]+W[i], DP[i-1])
print(DP[-1])

후기

블로그에 업로드한 첫 글이다.
많이 부족하지만 공부한 것들을 정리하는 용도로 열심히 해야겠다는 생각이 들었다.

또한, 최근에 본 나동빈님의 알고리즘 강좌가 문제를 풀이하는 데 큰 도움이 되었다.
책 발간 기념으로 무료로 라이브 강의를 하시니 참고하면 좋을듯하다.
https://www.youtube.com/watch?v=Lytj_xcw8mE&list=PLRx0vPvlEmdBFBFOoK649FlEMouHISo8N&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98

참고

https://www.acmicpc.net/problem/2156
https://www.acmicpc.net/board/view/11189