[백준/BOJ] 2156번 포도주 시식 (C/C++)

백준 온라인 저지(BOJ) 2156번 포도주 시식
https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

* 사용언어 : C언어, C++
 

1. 문제

일렬로 놓여진 포도주 N잔을 최대로 마실 수 있는 포도주의 양 출력
단, 연속으로 놓여진 3잔을 모두 마실 수 없음

 

2. 풀이

단계 별로 풀어보기 > 동적 계획법를 순서대로 풀던 중에서 가장 난항을 겪었던 문제입니다.
DP가 어느정도 익숙해졌다고 생각했는데 아직 갈 길이 먼 것 같습니다.
 
DP 배열을 2차원이나 3차원으로 선언하여 보다 직관적으로 푸는 방법도 있습니다.
저는 1차원으로 풀었기 때문에 코드는 간결하나 상대적으로 직관적이지는 않습니다.
 
 
1차원으로 풀기 위해서는 DP 배열에는 [해당 포도주까지 도달했을 때의 최대값]을 저장합니다.
해당 위치의 포도주를 안 마시는 선택지도 있기 때문에 도달했을 때라고 표현했습니다.
 
초기화 값은 dp[0]은 w[0], dp[1]은 w[0] + w[1], 그리고 dp[2]는 max(w[0] + w[1], w[0] + w[2], w[1] + w[2])입니다.
dp[4], dp[5]까지 직접 모든 Case를 손으로 그리면서 따져보면 규칙을 찾기가 더 쉬운데
어쨌든 dp[2]를 초기화하는 과정에서 dp 계산 시 3가지 선택지 중 하나를 골라야한다는 것을 알 수 있었습니다.
 
이를 일반화하여 아래와 같이 정리할 수 있었습니다.
1) dp[i - 1] (1번째 전까지의 최대값)
2) dp[i - 2] + w[i] (2번째 전까지의 최대값 + 이번 포도주)
3) dp[i - 3] + w[i - 1] + w[i] (3번째 전까지의 최대값 + 직전 포도주 + 이번 포도주)
 
 
dp 값을 계산하는 과정에 의미가 모호하게 녹아들어가 있어서 파악이 어려울 수 있는데
핵심은 2잔을 Skip하는 경우도 고려해야한다는 것입니다.
 
이와 관련있는 반례는 아래와 같습니다.
이 예제의 정답은 400(1, 2, 5, 6 선택)인데 2잔을 Skip할 수 없게 설계하면 301을 출력합니다.
 
6
100
100
1
1
100
100
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2156_포도주 시식
1188KB	0ms
*/
#include <cstdio>

const int LM = 10000;
int w[LM], dp[LM], N;

int max(int a, int b) { return a > b ? a : b; }
int max(int a, int b, int c) {
	int m = a;
	if (b > m) m = b;
	if (c > m) m = c;
	return m;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", &w[i]);

	dp[0] = w[0];
	dp[1] = w[0] + w[1];
	dp[2] = max(w[0] + w[2], w[0] + w[1], w[1] + w[2]);
	for (int i = 3; i < N; ++i) dp[i] = max(dp[i - 2] + w[i], dp[i - 1], dp[i - 3] + w[i - 1] + w[i]);

	printf("%d\n", max(dp[N - 1], dp[N - 2]));
	return 0;
}