백준 2156번: 포도주 시식(C++)

www.acmicpc.net/problem/2156

2156번: 포도주 시식

코드

#include <iostream>
using namespace std;

int n;
int wine[10001];
int dp[10001];

int max(int a, int b){
	return a > b ? a : b;
}

void init(){
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> wine[i];
	}
}

void solve(){
	dp[1] = wine[1];
	dp[2] = wine[1] + wine[2];
	dp[3] = max(max(dp[1] + wine[3], dp[1] + wine[2]), wine[2] + wine[3]);
	for(int i = 4; i <= n; i++){
        int n1 = dp[i-1];
        int n2 = dp[i-2] + wine[i];
        int n3 = dp[i-3] + wine[i] + wine[i-1];
        dp[i] = max(max(n1, n2), n3);
	}
	cout << dp[n];
}
int main() {
	init();
	solve();
	// your code goes here
	return 0;
}

 

문제

N개의 포도주 잔을 주어진 조건 하에서 가장 많이 마시는 방법? 방법이라기 보단 많이 먹는 양...?을 찾는 문제입니다.

처음 읽고서 느낀 점은 3번 연속으로 마실 수 없다 는 점에서 2579번: 계단 오르기와 비슷한 느낌을 받은 문제입니다.

www.acmicpc.net/problem/2579

2579번: 계단 오르기

wonsang98.tistory.com/71

2579번: 계단 오르기(백준 C++)

 

풀이

그래서, 처음에 문제 풀이 자체도 계단 오르기와 동일하게 진행했습니다.

배열 wine에는 차례대로 포도주의 양이 담겨있으며

배열 dp에는 포도주의 개수에 따른 주량?의 최대값을 찾아 넣습니다.

위와 같은 가정하에서 점화식을 2개로 생각했습니다.

dp[ i ] = dp[ i - 2 ] + wine[ i ]

dp[ i ] = dp[ i - 3 ] + wine[ i - 1] + wine[ i ] 

 

하지만 이렇게 풀게 되면, 오답이 됩니다.

왜냐하면 포도주를 2번 연속 안 먹는 경우가 고려되지 않았기 때문이죠.

이에 대한 반려로는 (100, 400, 2, 1, 4, 200) 이 주어지는 경우가 있습니다.

100, 400, 4, 200을 선택해서 704가 되어야 하지만 위의 점화식으로만 문제를 풀이하게 되면 2칸을 건너뛰지 못하기에

오히려 1을 선택하게 되는 바람에 더 큰수를 선택할 기회를 놓치게 되는 것이죠.

그렇기 때문에 선택하지 않는 것도 선택이다. 라고 생각하시면 될 것 같습니다.

 

• i - 3번째 까지 마신 포도주의 최댓값 + i-1 포도주 + i 포도주 
  • (i - 2)번째를 건너 뛰면서 3연속을 방지. 
• i - 2번째 까지 마신 포도주의 최댓값 + i포도주
  • (i - 1)번째를 건너 뛰면서 3연속을 방지.
• i - 2번째 가지 마신 포도주의 최댓값 + 1번째 마시지 않음.
  • 선택하지 않으면서 다음의 더 큰 수를 선택한다.

 

이렇게 3 개의 점화식을 토대로 DP를 전개하시면 풀 수 있는 문제입니다.