[BOJ][DP] 2156 - 포도주 시식

DP,, 점화식 생각해내기가 너무 어려운 것 같다,,

 

1. 문제

백준 2156 포도주 시식 문제

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

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

 

입력예시:

6
6
10
13
9
8
1

출력예시:

33

 

2. 문제풀이

먼저 입력 받는 값들을 저장하는 로직을 구현한다.

• 첫 줄에 포도잔의 개수 n이 주어지는데 이것을 input()함수를 사용하여 int로 형변환까지 하여 변수 n에 저장한다. 
• 그리고 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어지는데 이것은 반복문을 사용하여 값들을 하나씩 받아서 미리 정의해둔 리스트 안에 하나씩 순서대로 넣는다. 리스트에 값들을 저장할 때 포도잔의 index는 1부터 시작하면 생각하기 편하기 때문에 0번째 인덱스의 값은 미리 -1로 넣어두고 1번째 인덱스부터 입력받는 포도주의 양을 순서대로 저장하였다.

import sys

n = int(input())
data = [-1]
for _ in range(n):
  data.append(int(sys.stdin.readline()))

이제 입력 값들을 다 저장하였으니 그 값들을 사용하여 최대로 마실 수 있는 포도주의 양을 구하는 로직을 구현해보자.

 

"최대로 마실 수 있는 포도주의 양을 구한다" 제한 조건은 "연속으로 놓여있는 3잔을 모두 마실 수는 없다" 밖에 없다. 처음에는 이것을 '포도주를 3잔 마실 수 있는데 연속으로는 못 마신다'로 잘못 이해해서 삽질했던 기억이,,, :')  아무튼! 우리는  포도주를 원하는 만큼 마실 수 있는데 다만 연속으로 놓여있는 3잔은 못 마신다! 그러면 문제를 잘 이해했다고 생각하고 구현하는 부분으로 넘어가보자.

 

예시로 설멸하는 편이 나을 것 같아 위의 입력 예시를 가져왔다.

현재 포도주는 6, 10, 13, 9, 8 ,1의 양으로 순서대로 놓여져있다. 우리는 처음에 리스트에 -1 값을 넣어주고 입력값들을 저장했으므로 우리의 input data는 다음과 같이 저장되어 있다.

data: [-1, 6, 10, 13, 9, 8 ,1]

 

우리는 최대값을 구해야 하는데 나는 data 리스트를 하나씩 읽으면서 그 인덱스까지 마실 수 있는 최대 포도주의 양을 계산하여 dp 라는 새로운 리스트에 최대값을 저장하였다. 즉, 다시 말하면 지금 인덱스가 4번째 포도주 잔이라면, dp[4]에 포도주를 첫번째 잔 부터 4번째 잔까지 마실 수 있다고 생각했을 때 최대로 마실 수 있는 양을 dp[4]에 저장한 것이다. (여기서 4번째 잔은 마시는 것이 최대값일 수도 있고 안 마시는 것이 최대값일 수도 있다. 4번째 인덱스까지 도착했을 때의 최대값을 저장하는 것이지 4번째 잔을 마셨다고 가정하고 최대값을 저장하는 것이 아니기 때문이다.)

 

즉 나는 dp라는 리스트를 새로 만들어서 data 리스트에서 i번째 인덱스까지의 최대값(연속 3번은 제외)을 구해서 대응되는 dp[i]에 저장했다. 다만, data 리스트를 만들 때 0번째 인덱스는 사용하지 않기로 하고 -1 값을 넣어줬기에 dp의 0번째 인덱스에도 0을 넣어주었다.

dp = [0] * (n+1)

그래서 로직 시작 전 data 리스트와 dp 리스트에 저장된 값은 다음과 같다.

data: [-1, 6, 10, 13, 9, 8 ,1]

dp:     [0, 0, 0, 0, 0, 0, 0]

 

예시로 다시 처음부터 살펴보자.

• 1번째 인덱스까지 마실 수 있는 최대 포도주의 양은 당연히 1번째 포도주를 마시는 것이다. 그러므로 dp[1] 는 data[1]이다.
• 2번째 인덱스까지 마실 수 있는 최대 포도주 양은 또 당연하게도 1번째 포도주와 2번째 포도주를 모두 마시는 것이다. 2개 밖에 없기 때문에 우리는 "연속으로 놓여져 있는 3잔을 모두 마실 수는 없다"라는 제한사항을 신경 쓸 필요가 없다. 그러므로 dp[2]는 data[1] + data[2]이다.
• 3번째 인덱스까지 마실 수 있는 최대 포도주의 양을 계산할 때는 제한사항을 고려하여야 한다. 3개를 모두 다 마실 수 없기 때문이다. 그러면 경우의 수를 생각해보자. 마시면 O 안 마시면 X로 표시하겠다.

1. O O X

2. O X O

3. X O O

4. O X X

5. X O X

6. X X O

7. X X X

 

위와 같이 총 6개의 경우의 수가 존재한다. 하지만 매번 이렇게 경우의 수를 각각 다 계산할 수는 없다. 인덱스가 커질수록 경우의 수도 점점 늘어날 것이기 때문이다. 그렇기에 우리는 위의 경우들 중 비슷한 것들끼리 하나로 묶어서 생각해야 한다. 자세히 보면 현재 인덱스, 즉, 3번째 인덱스를 마시는 경우와 마시지 않는 경우로 나눌 수 있다.

• 3번째 인덱스를 마시는 경우: 2, 3, 6
• 3번째 인덱스를 마시지 않는 경우: 1, 4, 5, 7

- 3번째 인덱스를 마시지 않는 경우 중 하나하나 계산해보면 1번째 케이스인 "1, 2 번째 포도주를 모두 마시고 3번째 포도주를 마시지 않는 경우"가 최대값이다. 1번째 케이스는 2번째 인덱스(2 = 3 -1)까지 마실 수 있는 최대 포도주의 양, 즉, dp[2]와도 같다. 왜냐하면 3번째 포도주는 마시지 않기 때문에 없는거랑 같다. 그러면 우리는 여기서 i번째 인덱스의 포도주를 마시지 않을 때의 최대양은 i-1번째 인덱스에서의 마실 수 있는 최대양이라는 것을 알 수 있다. 즉 dp[i] = dp[i-1]이라는 것을 알 수 있다!

 

- 그러면 이제 3번째 인덱스를 마시는 경우를 조금 더 자세히 살펴보자. 3번째 포도주를 마시는 경우 제한사항을 신경 써야 하기 때문에 첫번째 잔이나 두번째 잔 중 하나만 마시거나 둘 다 안 마실 수 있다. 이 3가지 경우를 조금 더 확장시켜 3번째 인덱스가 아니라 i번째 인덱스를 마신다고 가정해보자. 그럼 다음과 같을 것이다. 앞에 많은 포도주가 있고 제한사항을 어기지 않을 때 i번째 인덱스까지 마실 수 있는 포도주의 최대 양을 계산해보자. ( 마지막 인덱스가 i이다.)

2. ? ? ? ? ? ? ? O X O

3. ? ? ? ? ? ? ? X O O

6. ? ? ? ? ? ? ? X X O

• 2번 케이스: i-2번째 잔까지 마실 수 있는 최대양(dp[i-2]) + i번째 잔의 포도주 양(data[i])
• 3번 케이스: i-3번째 잔까지 마실 수 있는 최대양(dp[i-3]) + i-1번째 잔의 포도주 양(data[i-1]) + i번째 잔의 포도주 양(data[i])
• 6번 케이스: i-3번째 잔까지 마실 수 있는 최대양(dp[i-3]) + i번째 잔의 포도주 양(data[i])

위의 경우들을 잘 생각해보면 포도주의 양은 항상 1,000 이하의 음이 아닌 정수(0보다 크거나 같다)기 때문에 6번 케이스는 절대 3번 케이스보다 클 수 없다. 그러므로 케이스 2, 3번 중 하나가 i번째 인덱스까지 마실 수 있는 최대 포도주의 양일 것이다. 이것을 코드로 쓰면 dp[i] = max(dp[i-2] + data[i], dp[i-3] + data[i-1] + data[i])이다.

 

즉, 이제 1-7번까지 모든 경우의 수를 생각했을 때 최대값을 구하는 과정은 다음과 같다.

1. i번째 포도주를 마시지 않을 때 최대값: dp[i-1]
2. i번째 포도주를 마실 때 최대값: max(dp[i-2] + data[i], dp[i-3] + data[i-1] + data[i])

그러므로, i번째 인덱스까지 마실 수 있는 포도주의 최대양은 max(dp[i-1], dp[i-2] + data[i], dp[i-3] + data[i-1] + data[i])이다. 즉, dp[i] = max(dp[i-1], dp[i-2] + data[i], dp[i-3] + data[i-1] + data[i])이다.

 

3. 총정리

• 입력 받은 값들을 data 리스트에 저장한다.
• dp 리스트에는 i번째 인덱스까지 마실 수 있는 포도주의 최대양을 저장한다. 이때, i번째 인덱스는 마실 수도 있고 안 마실 수도 있다.
• 그 마실 수 있는 최대양은 2가지 경우로 크게 나눌 수 있는데 i번째 인덱스를 마실 때, i번째 인덱스를 마시지 않을 때이다.
• i번째 인덱스를 마시면 최대값은 max(dp[i-2] + data[i], dp[i-3] + data[i-1] + data[i])이고 i번째 인덱스를 마시지 않으면 최대값은 dp[i-1]이다.
• 즉, 이 2가지 경우 중 더 큰 값이 i번째 인덱스까지 마실 수 있는 포도주의 최대양인 것이다. 이 값을 구해서 dp[i]에 저장한다.
• 위의 과정을 data의 마지막 인덱스까지 반복한다.

4. 최종 코드

import sys

n = int(input())
data = [-1]
dp = [0] * (n+1)
for _ in range(n):
  data.append(int(sys.stdin.readline()))


dp[1] = data[1]
if n >= 2:
  dp[2] = data[1] + data[2]

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

5. IndexError 런타임 에러 난 이유

사실 처음 제출할 때 런타임 에러가 났었는데 그 이유가 n이 3보다 작을 수 있는데 "if n>=2:"을 안 넣어줘서였다.

n의 범위는 (1 ≤ n ≤ 10,000) 이다!