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

1. 문제이해

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

n잔의 포도주와 각 포도주의 양이 주어질 때, 최대로 마실 수 있는 포도주의 양을 구하는 것이 목표이다.

(단, 선택한 포도주는 모두 마셔야 하며, 연속으로 3잔을 모두 마실 수 없다.)

 

 

 

2. 문제풀이

 

연속한 3잔을 마시지 않는 조건을 포함해, 최대로 마실 수 있는 포도주의 양을 구하는 문제이다.

문제의 뉘앙스만 봐도 이제는 DP문제임을 짐작 할 수 있다...

n번째 포도주의 양을 wine[n], n번째 포도주를 마실 때까지 마실 수 있는 최대 포도주 양을 drink[n]이라고 하자.

n번째 포도주를 마실 때까지 마실 수 있는 최대 포도주 양(drink[n])을 차례로 구해보면 다음과 같다.

 

 

1. 1번째 마실 수 있는 최대 포도주 양(drink[1]) 은 1번째 포도주만 마실 수 있으므로 wine[1]

(drink[1] = wine[1]))

 

2. 2번째 마실 수 있는 최대 포도주 양(drink[2])는 1번째, 2번째 포도주를 마시는 경우이므로 wine[1] + wine[2]

(drink[2] = wine[1] + wine[2]))

 

3. 3번째 마실 수 있는 최대 포도주의 양(drink[3])은 포도주 3잔을 연속해서 마실수는 없으므로,

1번째, 2번째 포도주를 마시고, 3번째 포도주를 마시지 않는 경우 (drink[2]와 동일)

1번째, 3번째 포도주를 마시는 경우 (drink[1] + wine[3])

2번째, 3번째 포도주를 마시는 경우 (drink[0] + wine[2] + wine[3]) (여기서 drink[0] = 0)

로 나누어 볼 수 있으며, 위 3가지 경우 중 가장 큰 값이 3번째 마실 수 있는 최대 포도주의 양(drink[3])이 된다.

(drink[3] = max(drink[2], drink[1] + wine[3], wine[2] + wine[3]))

 

4. 4번째 마실 수 있는 최대 포도주의 양(drink[4]) 또한 포도주 3잔을 연속해서 마실수는 없으므로,

3번째 포도주를 마실 때까지의 최대 포도주의 양을 먹고, 4번째 포도주는 마시지 않는 경우 (drink[3]과 동일)

1, 2번째 포도주를 먹고, 4번째 포도주를 마시는 경우 (drink[2] + wine[4])

1번째 포도주를 마시고, 3번째, 4번째 포도주를 마시는 경우 (drink[1] + wine[3] + wine[4])

로 나누어 볼 수 있으며, 위 3가지 경우 중 가장 큰 값이 4번째 마실 수 있는 최대 포도주의 양(drink[4])이 된다.

(drink[4] = max(drink[3], drink[2] + wine[4], drink[1] + wine[3] + wine[4]))

 

 

위 경우들을 토대로 점화식을 세워보면 다음과 같은 식을 구할 수 있다.

drink[n] = max(drink[n - 1], drink[n - 2] + wine[n], drink[n - 3] + wine[n - 1] + wine[n])

이를 토대로 작성한 코드는 아래와 같다.

 

 

 

3. 소스코드

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

int main() {
	int n;             // 포도주 잔의 개수 
	int wine[10000];   // 포도주의 양 
	int drink[10000];  // 최대로 마실 수 있는 포도주의 양

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

	drink[0] = wine[0];
	drink[1] = wine[0] + wine[1];
	drink[2] = max(drink[1], max(drink[0] + wine[2], wine[1] + wine[2]));

	// max는 매개변수가 2개이므로, 2개를 비교후 큰값을 나머지와 비교하는 방식 사용
	for (int i = 3; i < n; i++) {
		drink[i] = max(drink[i - 1], 
		max(drink[i - 2] + wine[i], drink[i - 3] + wine[i - 1] + wine[i]));
	}

	cout << drink[n - 1];

	return 0;
}

2. 문제풀이에서 도출한 방식에 따라 작성한 코드이다.

wine, drink라는 배열을 두고, 각각 포도주의 양과 최대로 마실 수 있는 포도주의 양으로 정의했다.

 

배열은 0부터 시작하므로, 처음 시작하는 포도주를 0번째로 정의했다.

0번째, 1번째, 2번째 마실 수 있는 최대 포도주의 양은 위에서 정의한 것과 동일하게 초기화 해주었다.

( drink[0] = wine[0], drink[1] = wine[0] + wine[1]

drink[2] = max(drink[1], drink[0] + wine[2], wine[1] + wine[2]) )

 

위와 같이 기본값들을 정의해준 뒤, 최종적으로 도출해낸 점화식을 이용해

n - 1번째 까지 마실 수 있는 최대 포도주의 양을 구해준다.

( drink[n] = max(drink[n - 1], drink[n - 2] + wine[n], drink[n - 3] + wine[n - 1] + wine[n]) )

 

 

---

DP문제도 조금 감이 잡혀가는 것 같기도 하고..?🥺

아직 멀었지만.. DP마스터가 될때까지 열심히 해야지👊