백준 : 포도주 시식(2146) with 파이썬

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

2156번: 포도주 시식

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

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

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

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

 

문제풀이

첫째 줄에 포도잔의 개수 n이 주어진다. ( 1 <= n <= 10,000)

와인잔의 수 n = 6 이라고 가정해보겠다.

위 그림을 dp로 나열해 보면

dp[1] = 6 

dp[2] = 10

dp[3] = 13 

dp[4] = 9 

dp[5] = 8 

dp[6] = 1
이와 같이 저장되는 것을 알 수 있다.

여기서 조건을 보면 와인 3잔을 연속으로 마실 수 없다는 조건이 있으므로 점화식을 이용해서 dp[n]이 가질 수 있는 최댓값을 구해볼 것이다.

최댓값을 구하기 위해서는 먼저 dp를 생성해서 [0] * 10001 조건의 범위만큼 초기화를 해주고 dp[1], dp[2]는 값이 변하지 않으므로 정의를 한 뒤 반복문을 사용하여 (3 ~ n + 1)까지의 값을 최댓값으로 받아서 dp[n]을 구하면 될 것 같다.

 

import sys

input = sys.stdin.readline

n = int(input())

drink = [0] * 10001

for i in range(1, n + 1):

     drink[i] = int(input())

 

dp = [0] * 10001

dp[1] = drink[1]

dp[2] = drink[1] + drink[2]

for i in range(3, n + 1):

     dp[i] = max(dp[i - 3] + drink[i - 1] + drink[i], dp[i - 2] + drink[i], dp[i - 1])

print(dp[n])

코드 하나하나 설명 들어갑니다.

import sys

sys 모듈 : 시스템과 관련된 함수와 변수들을 제공하여 파이썬 프로그램이 운영 체제와 상호 작용하고 정보를 얻을 수 있게 도와줍니다. 

sys.stdin

sys.stdin : sys 모듈 내에 있는 표준 입력 스트림을 나타내는 객체입니다. 표준 입력 스트림은 사용자가 키보드로 입력하는 데이터를 읽어오는 용도로 사용됩니다.

input = sys.stdin.readline

sys.stdin.readline : 표준 입력 스트림에서 한 줄을 읽어오는 함수입니다. 이 함수를 호출하면 사용자가 입력한 데이터 중에서 한 줄을 읽어와 문자열로 반환합니다. 입력이 없을 때까지 기다릴 수 있습니다.

n = int(input())

n 에 와인잔의 수를 입력 받습니다.

drink = [0] * 10001

drink 객체를 생성하여 조건의 범위만큼 초기화합니다.

for i in range(1, n + 1):

     drink[i] = int(input())

반복문을 사용하여 와인의 양을 입력받습니다.

dp = [0] * 10001

dp 객체를 생성하고 조건의 범위만큼 초기화합니다.

dp[1] = drink[1]

dp[2] = drink[1] + drink[2]

dp[1]과 dp[2]는 점화식 조건에서 불변하므로 먼저 정의해줍니다.

for i in range(3, n + 1):

dp[i] = max(dp[i - 3] + drink[i - 1] + drink[i], dp[i - 2] + drink[i], dp[i - 1])

print(dp[n])

반복문을 활용하여 dp[i]를 구해줍니다. 이때 최댓값을 구하기 위해서 파이썬에서 제공하는 함수 max()를 사용했습니다.

이 코드를 자세히 보면 i = 3 이라고 가정할 경우,

dp[i] = max(dp[0] + drink[2] + drink[3],      -> 0 + 전 와인 + 현재와인 

                     dp[1] + drink[3],                         -> 전전 와인 + 현재와인 

                     dp[2])                                           -> 전전 와인 + 전와인 

 

위 3가지 경우를 비교하여 점화식으로 dp[i]를 구하면 와인양의 최댓값을 구할 수 있을 것입니다

이 문제는 계단 오르기(2579)문제와 매우 유사한데 계단 오르기 문제와의 차이점은 마지막 계단을 밟아야한다는 조건이 없다는 것이 차이점입니다. 계단 오르기에서는 1, 3, 2, 3 경우 밖에 없지만 와인 문제에서는 13, 12, 23 세가지 경우의 수가 존재하기 때문에 dp[i - 1]이 추가된 것입니다.