728x90
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고
www.acmicpc.net
문제조건
DP 문제
현재 마실 수 있는 포도주를 wine[i], 현재가 최대일 경우를 저장해놓은 배열을 dp[i]라고 하자.
연속으로 3잔을 마실 수 없으므로 3잔씩 끊어서 생각해보자!!
1) 현재 포도주를 마시지 않는 경우 (o o x) : dp[i-1]
2) 현재 포도주를 마시고 이전 포도주를 마시지 않는 경우 (o x o) : dp[i-2] + wine[i]
3) 현재와 이전 포도주를 모두 마시는 경우 (x o o) : dp[i-3] + wine[i-1] + wine[i]
위 세가지 경우를 모두 비교해서 최대값을 찾으면 끝난다.
[C++]
#include <iostream>
#include <algorithm>
using namespace std;
int N, wine[10001], dp[10001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> wine[i];
}
dp[1] = wine[1];
dp[2] = wine[1] + wine[2];
int result = 0;
for (int i = 3; i <= N; i++) {
result = max(dp[i - 1], wine[i] + dp[i - 2]);
result = max(result, dp[i - 3] + wine[i - 1] + wine[i]);
dp[i] = result;
}
cout << dp[N] << "\n";
return 0;
}
[Python]
N = int(input())
wine = []
for _ in range(N):
wine.append(int(input()))
# n번째 잔을 마실 경우
# 1) n-1 번째 마신 경우 => n-2번째 잔은 마실 수 없음
# 2) n-1 번째 마시지 않은 경우 => n-2번째 잔을 마실 수 있음
# n번째 잔을 마시지 않을 경우
dp = [0] * N
dp[0] = wine[0]
if N > 1:
dp[1] = wine[0] + wine[1]
if N > 2:
dp[2] = max(wine[2] + wine[1], wine[2] + wine[0], dp[1])
for i in range(3, N):
dp[i] = max(dp[i - 3] + wine[i - 1] + wine[i], dp[i - 2] + wine[i], dp[i - 1])
print(dp[N - 1])728x90
