[백준] 2156번 포도주 시식 (파이썬)

< 백준 2156번 포도주 시식 - 파이썬 풀이 >

• 해당문제 링크

목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 먼저 해당 문제는 가능한 많은 양의 포도주를 맛봐야하는 최적화 문제이다.
• 무작정 백트래킹과 같이 모든 경우의 수를 생각해볼수 있으나 잔의 개수가 최대 10,000개 이기 때문에 시간 초과 발생할 것으로 생각된다.
• 그렇다면 DP를 이용해서 풀어야겠다고 생각했다.
• DP의 최적문제는 이전 저장된 값들을 이용해서 이후의 최적의 값을 찾는 것이다.
• 그렇게 하기 위해서 바텀업을 하면서 반복하여 푸는 방식을 이용할 것인데 이 경우 작은 문제에서 큰 문제를 풀기 때문에 작은 경우를 생각해보는 것이 좋다고 생각한다.
• 해당 문제는 3개 연속으로 와인을 마시지 못한다. 이를 알아두고 작은 경우를 생각해보겠다.
• 잔이 1개인 경우, 와인을 젤 많이 먹으려면 어떻게 해야할까? 잔 1개를 마시면 된다. 잔이 2개인 경우는?? 이때도 마찬가지로 다 마시면 된다. => 이것들을 이용해서 seed 값을 삽입.
• 잔이 3개인 경우, 이때부터 달라지는데 1,2,3 이렇게 잔의 번호가 있다면 1,3 / 2,3 / 1,2 중에서 가장 큰 양을 마시면 된다. => 요 느낌으로 iterate
• 이걸 쭉 한다고 생각을 해보자. 마지막 세 개의 원소가 남았다고 가정하면 .... N-2, N-1, N 요렇게 생각할 수 있다. 여기서 어떤 경우를 생각해야할까?
  • 첫번째, N-1과 N을 더하고 N-2 이전까지의 최대 더한 값과 더해주는 방법.
  • 두번째, N-2까지 최대 더한 값과 N을 더해주는 방법.
  • 세번째, 그냥 N-1까지 최대 더하는 방법.
• 이 경우들과 seed 값을 이용해서 iterate를 해주면 된다.

구현코드

def solution():
    dp[1] = grape[1] # seed 넣기
    if n == 1: # seed를 2까지 넣어주기 때문에 indexerror 발생가능.
        return dp[1]
    dp[2] = dp[1] + grape[2] # seed 넣기 (잔 2개까지는 그냥 다 마시면 됨)
    for i in range(3, n + 1): # iterate
        dp[i] = max(dp[i - 1], dp[i - 2] + grape[i], dp[i - 3] + grape[i - 1] + grape[i])
        # dp[i-1] = n-1까지 최대 더한 값, dp[i-2] + grape[i] = n-2까지 최대 더한 값과 n의 원소값을 더한 값, dp[i-3] + graph[i-1] + grape[i] = n-1과 n의 원소값을 더하고 n-2 이전까지의 최대 더한 값과 더한 값.
    return dp[n]
if __name__ == "__main__":
    n = int(input())
    grape = [int(input()) for _ in range(n)]
    grape = [0]+grape
    dp = [0] * (n + 1)
    print(solution())