[C++] 백준 2156번: 포도주 시식

문제 바로가기

2156번: 포도주 시식

개요

대표적인 다이내믹 프로그래밍 분류 문제이다.

문제를 푸는 방법은 점화식을 찾고 구현하는 것.

N이 최소일 때부터 손으로 써가며 규칙을 찾는 것이 중요하다.

풀이

N이 1일 때부터의 경우를 차근차근 생각해보자

i번째 잔에 들어있는 포도주의 양을 W[i],

i번째 잔까지 마실 수 있는 포도주의 최대값을 S[i]라고 하면 아래와 같이 나타낼 수 있다.

N	잔을 선택하는 경우	식
1	●	W[0]
2	● ●	W[0] + W[1]
3	● ● ○	S[i - 1]
	● ○ ●	S[i - 2] + W[i]
	○ ● ●	W[i - 1] + W[i]
4	○ ● ● ○	S[i - 1]
	● ● ○ ●	S[i - 2] + W[i]
	● ○ ● ●	S[i - 3] + W[i - 1] + W[i]

N이 4일 때의 식을 보면, i번째 와인잔까지의 마실 수 있는 포도주의 최대값은 3개의 식 중 최대값으로 정해진다.

\(ⅰ. S[i - 1]\)

\(ⅱ. S[i - 2] + W[i]\)

\(ⅲ. S[i - 3] + W[i - 1] + W[i]\)

이게 답이다. 그대로 코드로 옮기면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; i++)
#define INF 987654321
#define EL "\n"

int main() {
	FAST_IO;

	int N;
	cin >> N;

	vector<int> W(N);
	FOR(i, N)
		cin >> W[i];

	vector<int> S(N);
	S[0] = W[0];
	S[1] = W[0] + W[1];
	S[2] = max(max(S[1], S[0] + W[2]), W[1] + W[2]);
	for (int i = 3; i < N; i++)
		S[i] = max(max(S[i - 1], S[i - 2] + W[i]), S[i - 3] + W[i - 1] + W[i]);

	cout << S.back() << EL;

	return 0;
}