[백준] 2156 포도주 시식
문제 설명
문제를 살펴보면, 연속으로 놓은 포도주를 2번까지만 마실 수 있고, 연이은 두개를 마시는 경우에는 무조건 하나를 건너뛰어야 한다는 점을 알 수 있다.
문제 풀이
동적 계획법을 사용하여 풀 수 있다. 점화식만 잘 세우면 크게 어렵지 않은 문제이기 때문에 점화식을 잘 세우고 Bottom-Up 방식으로 cache를 채워서 최적해를 구하는 방식으로 진행하면 된다.
우선 입력받는 포도주의 값들을 배열로 정리해준다.
이 때, 인덱스 관리를 쉽게 하기 위해 첫 인덱스(0)에는 0을 넣어주고 시작한다.
이후, 순차적으로 포도주가 있는 잔들을 지나간다고 생각하며,
해당 포도주를 마셨을 때와 마시지 않았을 때를 생각해서 해당 시점에서의 최대값을 저장할 cache 배열을 생성한다.
이 cache배열(코드에는 max_drinking)을 각 포도주들의 위치와 매핑시켜주기 위해 첫 인덱스의 값은 0으로 둔다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N = int(input())
# 포도주의 가치를 저장할 배열
wine = [0]
for _ in range(N):
wine.append(int(input()))
# --- 위까지가 입력값 --- #
max_drinking= [0 for _ in range(N+1)]
#초기값 설정
max_drinking[1] = wine[1]
if N > 1:
max drinking[2] = wine[1] + wine[2]
해당 문제에서 i번째 포도주에 왔을 때 고려할 수 있는 선택지는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
# i번째 포도주를 마시지 않아 그 전 값과 같을 때
# (직전 두 잔을 모두 마시는 것이 i번째를 마시는것보다 이득인 경우)
max_drinking[i] = max_drinking[i-1]
# i-1번째 포도주를 마시지 않고 i번째 포도주를 마시는 경우
max_drinking[i] = max_drinking[i-2] + wine[i]
# i-1번째 포도주와 i번째 포도주를 마시는 경우
# (이 때는 i-2번째 포도주를 건너뛰었다는 말이 된다)
max_drinking[i] = max_drinking[i-3] + wine[i-1] + wine[i]
각 경우의 수를 시각적으로 표현해보자.
O는 해당 포도주를 마신 것이고, X는 해당 포도주를 마시지 않은 것이다.
첫 번째 경우: | i-3 | i-2 | i-1 | i |
| X | O | O | X |
두 번째 경우: (이 부분이 살짝 까다로운데, max_drinking[i-1]의 시점에서 생각해보면,
i-1번째 포도주를 안 마셨다는 것은 해당 시점에 위의 첫 번째 경우를 선택했다는 말이며, 이는 그 직전 두 잔을 마셨다는 말이다)
| i-3 | i-2 | i-1 | i |
| O | O | X | O |
세 번째 경우:
| i-3 | i-2 | i-1 | i |
| O | X | O | O |
이 중 최대값을 구하여 max_drinking dpcache에 넣어준다.
1
2
3
4
5
for i in range(3, N + 1):
max_drinking[i] = max(
max_drinking[i - 1],
max_drinking[i - 2] + wine[i],
max_drinking[i - 3] + wine[i - 1] + wine[i]
최종 코드
위의 개념들과 코드들을 잘 정리해서 작성하면 아래와 같은 최종 코드가 나온다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N = int(input())
wine = [0] # 포도주 양을 저장할 리스트
for _ in range(N):
wine.append(int(input()))
# 각 포도주 양을 마실 때의 최대 양을 저장할 리스트
max_drinking = [0 for _ in range(N + 1)]
# 초기값 설정
max_drinking[1] = wine[1]
if N > 1:
max_drinking[2] = wine[1] + wine[2]
# 동적 프로그래밍을 통한 최대 양 계산
for i in range(3, N + 1):
max_drinking[i] = max(
max_drinking[i - 1], # i번째 잔을 마시지 않는 경우
max_drinking[i - 2] + wine[i], # i번째 잔을 마시는 경우
max_drinking[i - 3] + wine[i - 1] + wine[i] # i-1번째와 i번째 잔을 연속해서 마시는 경우
)
# 결과 출력
print(max_drinking[N])