[DP] 백준 문제 풀이 - 2156 포도주 시식

👩🏻‍💻 문제링크

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

2156번: 포도주 시식

 

✍️ 아이디어

1. 문제 이해

• 포도주 n개가 일렬로 정렬되어 있고 각 잔에 들어있는 포도주의 양을 입력받을때 포도주를 가장 많이 먹을때 얼마나 먹는가
• 조건 : 인접한 포도주 3잔을 연속으로 들이키면 안됨  

2. 나는 조건을 2개로 생각해 3차원 배열을 만듬 (2번째는 바로 전 포도주를 마신여부, 3번째는 전전 포도주를 마신 여부)

3. 생각보다 케이스가 복잡함

• 첫 잔을 안마시는 경우
• 마지막 잔을 안마시는 경우
• 첫 잔 마지막 잔 둘다 안마시는 경우
• 최대한 많은 잔을 마시는 경우
• 두 잔 연속으로 안마시는 경우★ -> 처음에 이걸 간과함

6 1000 1000 1 1 1000 1000

4. D[N][2][2] = N번째까지 포도주를 마셨을때 최댓값 (전꺼, 전전꺼 포도주를 마신경우를 3차원 배열로 기록)

5. DP[i - 3] + Arr[i - 1] + Arr[i] // DP[i - 2] + Arr[i] // DP[i - 1]  이렇게 3개를 비교하면 끝나는 거였음

• Wine[N] 번째 잔을 마신다.
  • Wine[N - 1] 번째 잔을 마셨을 경우 xoo
    • Wine[N - 1] 번째 잔과 Wine[N] 번 째 잔까지 총 2 잔을 마셨으므로, 더 이상의 잔을 더할 순 없다.
    • 따라서, D[N] 은, [N - 3] 번째 잔까지 마신 포도주의 양 D[N - 3] 에, [N - 1] 번째 잔의 양 Wine[N-1] 과 N 번째 잔의 양 Wine[N] 을 더해서 계산한다.
      • D[N] = D[N - 3] + wine[N - 1] + wine[N]
  • Wine[N - 1] 번째 잔을 마시지 않았을 경우 ?xo
    • [N - 2] 번째 잔까지 마신 포도주의 양 D[N - 2] 에, N 번째 잔의 양 Wine[N] 을 더해서 계산한다.
      • D[N] = D[N - 2] + wine[N]
  • 마지막으로, 둘 중에 어느 경우가 더 마신 경우인지 모르기 때문에, 더 큰 값을 가려낸다.
    • D[N] = max(D[N - 3] + wine[N - 1] + wine[N], D[N - 2] + wine[N])
• Wine[N] 번째 잔을 마시지 않는다. ??x
  • Wine[N - 1] 번째 잔까지 탐색했을 때의 마실 수 있는 최대 양을 그대로 사용한다.
    • D[N - 1]

✍️소스코드

• 내코드
• 0 = 전꺼 포도주 마심,  1 = 전꺼 포도주 안마심
• 너무 무대뽀 구현 느낌이 남

#include <iostream>
#include <algorithm>
using namespace std;
long long result[10001][2][2];
int value[10001];
int main()
{
	int n; cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>value[i];
	}
	result[1][0][0]= value[1];
	result[1][0][1]= value[1];
	result[1][1][0]= value[1];
	result[1][1][1]= value[1];
	result[2][0][0]= value[1]+value[2];
	result[2][0][1]= value[1]+value[2];
	result[2][1][0]= value[2];
	result[2][1][1]= value[2];
	for(int i=3; i<=n; i++)
	{
		result[i][0][0]= result[i-1][0][1];
		result[i][0][1]= max(result[i-1][1][0],result[i-1][1][1]) + value[i];
		result[i][1][0]= max(result[i-2][1][1],max(result[i-2][1][0],result[i-2][0][1])) + value[i];
		result[i][1][1]= max(max(result[i-2][0][0],result[i-2][0][1]),max(result[i-2][1][0],result[i-2][1][1])) + value[i];
	}
	
	cout<<max(max(result[n][0][0],result[n][0][1]),max(result[n][1][1],result[n][1][0]))<<'\n';
}

 

• 다른사람 코드
• 이친수 문제랑 비슷하다는데 이친수는 하나 전만 보면 되는데(11만 안나오면 됨) 이건 두개 전까지 봐야함(샷샷샷 나오면 안됨)

#include <iostream>
using namespace std;
int a[10001];
int d[10001];
int main() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    d[1] = a[1];
    d[2] = a[1]+a[2];
    for (int i=3; i<=n; i++) {
        d[i] = d[i-1]; // 기본적으로 전꺼 전전꺼 둘다 마신 경우를 전제로 함
        if (d[i] < d[i-2] + a[i]) // 전꺼를 안마신 경우
        {
            d[i] = d[i-2] + a[i];
        }
        if (d[i] < d[i-3] + a[i] + a[i-1]) // 전전꺼를 안마신 경우
        {
            d[i] = d[i-3] + a[i] + a[i-1];
        }
    }
    printf("%d\n",d[n]);
    return 0;
}

 

 

체감난이도	걸린시간	참고	사용 문법
상	50min	x	3차원 DP