[백준] 2156. DP_포도주시식 - Python

문제

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

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

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

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

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

-----------------------------------------------------------------------------------------------------------------------------------

★ 시작하기 전에

DP 문제인걸 알고 시작하는 것.. 모르고 시작하는 것... 에 따라 시간은 천차만별일 것 같다.

다만, DP인 것에 대한 힌트는 단계별 연관 관계를 파악하는 것이 중요하다.

 

하나씩 보면, 처음에는 하나만 먹은게 최대

두번째도, 처음꺼 먹고 두번째꺼 먹은게 최대

세번째 부터.. 고민이 시작된다.

1. 1, 3번 먹은 경우

2. 3번 먹고 2번 먹은 경우(3이후의 경우에는 전전전 최댓값을 더해야 한다)

 

이 규칙을 손으로 써보면서 풀면 알 수 있다. 느끼기 전까진... ;;

 

import sys

input = sys.stdin.readline

n = int(input())
before = 0
dp = [0 for _ in range(n)]
for i in range(n):
    m = int(input())
    if i == 0:
        dp[0] = m
        continue
    elif i == 1:
        dp[1] = dp[0] + m
    else:
        str1 = m + dp[i-2]
        str2 = m + before
        # str2의 경우 현재, 그리고 이전껄 먹으므로 전전꺼는 먹으면 안된다.
        if i - 3 >= 0:
            str2 += max(dp[:i-2])
        dp[i] = max(str1, str2)
    before = m
print(max(dp))

dp 문제가 쉬울 수 있는 부분은 규칙을 잘 찾아내는 경우이다.

dp임을 깨닫고 탐욕 알고리즘 처럼 하나씩 해나가면, dp를 깨닫고 점화식 및 규칙을 찾아낼 수 있다.