[백준] 2156번 포도주 시식

단계별로 풀어보기 동적 계획법 1의 10단계 문제

2156번: 포도주 시식

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* grape = new int[n];
	int** dp = new int*[n];
	for (int i = 0; i < n; i++) {
		dp[i] = new int[2];
	}
	for (int i = 0; i < n; i++) {
		cin >> grape[i];
	}
	dp[0][0] = grape[0];
	dp[0][1] = grape[0];
	if (n > 1) {
		dp[1][0] = grape[0] + grape[1];
		dp[1][1] = grape[1];
	}
	for (int i = 2; i < n; i++) {
		dp[i][0] = dp[i - 1][1] + grape[i];
		int max = 0;
		for (int j = i - 2; j >= 0; j--) {
			for (int k = 0; k < 2; k++) {
				if (dp[j][k] > max) {
					max = dp[j][k];
				}
			}
		}
		dp[i][1] = max + grape[i];
	}
	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			if (dp[i][j] > max) {
				max = dp[i][j];
			}
		}
	}
	cout << max << endl;
	return 0;
}

배열 dp[i][0]에는 i-1번째 포도주를 마셨을 경우 최대 양을, dp[i][1]에는 i-1번째 포도주를 마시지 않았을 경우 가능한 최대 양을 저장했다.

2579번 계단오르기와 다른 점은 계단 오르기 문제는 반드시 마지막 계단을 밟아야 하지만 이 문제는 반드시 마지막 포도주를 마실 필요가 없다. 또, 계단오르기는 무조건 한 칸이나 두 칸씩 올라야 하지만 포도주 마시기는 여러 포도주를 뛰어넘고 안 마셔도 상관이 없다. 따라서 이 문제가 더 고려할 것이 많아 조금 더 복잡하다.

 

이렇게 2020년에 1월 24일에 풀고 두 달 반 후인 4월 11일에 다시 한 번 풀어보았다.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	vector<tuple<int, int, int>> dp(n);
	dp[0] = make_tuple(0, v[0], v[0]);
	if (n > 1) {
		dp[1] = make_tuple(v[0], v[1], v[0] + v[1]);
	}
	for (int i = 2; i < n; i++) {
		get<0>(dp[i]) = max(get<0>(dp[i - 1]), max(get<1>(dp[i - 1]), get<2>(dp[i - 1])));
		get<1>(dp[i]) = get<0>(dp[i - 1]) + v[i];
		get<2>(dp[i]) = get<1>(dp[i - 1]) + v[i];
	}
	cout << max(get<0>(dp[n - 1]), max(get<1>(dp[n - 1]), get<2>(dp[n - 1])));
	return 0;
}

코드 길이도 더 짧고 시간도 더 적게 걸렸고 메모리도 더 적게 사용했다.

나는 잘 모르겠어도 나도 모르는 사이에 발전은 하나보다.

3-tuple을 만들어서 dp 벡터에 저장했다.

dp[i]에 저장된 튜플의 첫 번째 원소는 i번째 포도주를 마시지 않는 경우 중 최댓값을 저장한다. i번째 포도주를 마시지 않으므로 dp[i]에 저장된 3가지 숫자 중에 가장 큰 수를 그대로 가져온다.

dp[i]에 저장된 튜플의 두 번째 원소는 i번째 포도주를 마시되 i - 1번째 포도주는 마시지 않았을 경우 중 최댓값을 저장한다. i - 1번째 포도주는 마시지 않았어야 하므로 dp[i - 1]의 첫 번째 원소에 i번째 포도주를 더해준 값을 저장한다.

dp[i]에 저장된 튜플의 세 번째 원소는 i번째 포도주 연속으로 마시는 경우이다. 세 개를 연속으로 마시지는 못하므로 dp[i - 1]의 두 번째 원소에 i번째 포도주를 더해준 값을 저장한다.