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

 

 

<DP코드>

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

int n;
int wine[10001];
int DP[10001];

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

	DP[1] = wine[1];
	DP[2] = wine[1]+wine[2];

	for (int i = 3; i <= n; i++)
		DP[i] = max(max(DP[i - 2] + wine[i], DP[i - 3] + wine[i] + wine[i - 1]),DP[i-1]);

	cout << DP[n];
	
}

 

 

점화식을 생각해보면 3가지 경우로 나눌 수 있다.

• i번째 와인을 마시는 경우 => wine[i] + DP[i-2]
• i-1번째 와인과 i번째 와인을 마시는 경우 => wine[i-1] + wine[i] + DP[i-3]
• i번째 와인을 마시지 않는경우 => DP[i-1]

따라서 위의 세 경우중 가장 큰 수를 택하면 DP[i]값을 구할 수 있게 된다.

 

예제입력1로 예를 들자면 먼저 DP 초기값 1번째와 2번째를 구하면

/	1번째	2번째	3번째	4번째	5번째	6번째
wine	6	10	13	9	8	1
DP	6	16	.	.	.	.

 

그런다음 3번째의 경우

• wine[3] + DP[3-2] = 13 + 6 = 19
• wine[3-1] + wine[3] + DP[3-3] = 10 + 13 + 0 = 23
• DP[3-1] = 16

/	1번째	2번째	3번째	4번째	5번째	6번째
wine	6	10	13	9	8	1
DP	6	16	23	.	.	.

DP[3] = 23이다.

 

4번째의 경우

• wine[4] + DP[4-2] = 9 + 16 = 23
• wine[4-1] + wine[4] + DP[4-3] = 13 + 9 + 6 = 28
• DP[4-1] = 23

/	1번째	2번째	3번째	4번째	5번째	6번째
wine	6	10	13	9	8	1
DP	6	16	23	28	.	.

DP[4] = 28이다.

 

5번째의 경우

• wine[5] + DP[5-2] = 8 + 23 = 23
• wine[5-1] + wine[5] + DP[5-3] = 9 + 8 + 16 = 33
• DP[5-1] = 28

/	1번째	2번째	3번째	4번째	5번째	6번째
wine	6	10	13	9	8	1
DP	6	16	23	28	33	.

DP[5] = 33이다.

 

6번째의 경우

• wine[6] + DP[6-2] = 1 + 28 = 29
• wine[6-1] + wine[6] + DP[6-3] = 8 + 1 + 23 = 32
• DP[6-1] = 33

/	1번째	2번째	3번째	4번째	5번째	6번째
wine	6	10	13	9	8	1
DP	6	16	23	28	33	33

DP[6] = 33이다.

 

 

 

 

 

www.acmicpc.net/problem/2156

2156번: 포도주 시식