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

문제 : www.acmicpc.net/problem/2156

2156번: 포도주 시식

주어진 포도주의 양 중에서 조건을 만족하면서 최대로 마실 수 있는 양을 계산 하는 문제이다.

조건은 한번 고른잔은 다 마셔야 하고, 연속으로 3잔을 골라 마실 수 없다는 것이다.

 

어떻게 접근해야 할지 생각하다가 도저히 감이 잡히지 않아 결국 검색을 하게 되었다.

 

참조한 블로그 : mygumi.tistory.com/98

백준 2156번 포도주 시식 [DP] :: 마이구미

글을 읽고나니 마지막잔을 기준으로 접근해야 한다는 것을 알게되었다. 그리고 아무리 생각해도 감이 안잡히면 시간 허비하지말고 검색해서 도움받는게 정신건강과 시간에 효율적이다라는 생각도 들었다.

 

접근 (검색을 통해 도움을 받음)

마지막잔을 마시면 생각할 수 있는 경우는 두가지가 있다.

 

1. 마지막잔의 직전 잔도 마셨다.

2. 마지막잔의 직전 잔을 마시지 않았다.

 

잔의 수를 N이라고 하면 마지막잔은 N번째 잔이 될것이다.

방금 이야기한 마지막잔을 마셨을때 생각할 수 있는 경우에 대한 식을 생각해보면 다음과 같다.

 

N >= 3 이고, 각 잔에 담긴 포도주의 양을 담는 배열을 ia라고 하고

잔의 개수에 따른 최대 포도주의 양을 담는 배열 (dp배열)을 sa라고 한다면,

 

1번의 경우 : sa[N] = sa[N-3] + ia[N-1] + ia[N] 이 된다.

 

예를 들어 잔이 6잔이 있고 각 잔에 6 10 13 9 8 1 이 있다면,

마지막잔(6번째 잔)과 그 직전 잔(5번째 잔)을 모두 마시면 4번째 잔은 마실 수 없으므로 제외하고 3번째 잔까지의 최대 포도주의 양을 계산하는 경우이다.

 

즉 3번째 잔까지의 최대 포도주의 양 + 5번째 포도주의 양 + 6번째 포도주의 양이

잔이 6잔일때 마지막잔과 그 직전잔을 마셨을때 최대 포도주의 양이 된다.

 

2번의 경우 : sa[N] = sa[N-2] + ia[N] 이 된다.

 

앞선 1번의 설명처럼 잔이 6잔이 있고 각 잔에 6 10 13 9 8 1 이 있다면,

마지막잔(6번째 잔)을 마시고, 마시지 않은 직전 잔(5번째 잔)을 제외하고 4번째 잔까지의 최대 포도주의 양을 계산하는 경우이다.

 

즉 4번째 잔까지의 최대 포도주의 양 + 6번째 포도주의 양이

잔이 6잔일때 마지막잔과 그 직전잔을 마셨을때 최대 포도주의 양이 된다. (5번째 잔은 마시지 않았으므로 연산에 포함하지 않는다.)

 

여기서 1번의 경우와 2번의 경우 두가지 중에서 최대 값이 sa[N]의 값이 된다.

 

그런데, 이렇게만 계산하면 잘못된 결과가 나온다.

 

잔이 6잔이고 각 잔의 양이 123 456 1 2 10 111 일 경우에 위에서 언급한 식대로 sa값을 계산하면

sa[1] = 123, sa[2] = 579, sa[3]이 457이 나온다. 사실 sa[3]은 579이어야 한다.

 

즉, 앞선 점화식으로 계산한 sa[N]의 값이 sa[N-1]보다 작으면 sa[N]은 sa[N-1]의 값이어야 한다.

최대값을 계산하는 문제인데 이전의 최대값보다 적은 값이 최대값이 되면 안되니까!

 

이 이야기는 곧 연속으로 안마실수 있는 경우도 있다라는 의미가 된다.

 

최종적으로 N번째 잔 (N >= 3)의 최대 포도주의 양은 앞선 1번의 경우와 2번의 경우 중 최대 값을 먼저 계산 후 N-1잔까지의 최대 포도주의 양 중에서 최대값을 저장하면 된다.

 

코드

C++ : github.com/devdinist/BOJ_Code/blob/master/Cpp/DP/BOJ2156.cpp

JAVA : github.com/devdinist/BOJ_Code/blob/master/Java/Sort_Algorithm/DP/BOJ2156.java