이 문제를 풀 때, Top-down 방식
대신 Bottom-up 방식
으로 풀어야겠다는 생각까지는 떠올렸으나, 이후 '연속으로 놓여 있는 3잔을 모두 마실 수는 없다' 라는 조건이 굉장히 까다롭게 느껴져서 풀이에 애를 먹고 있었다. 결국 질문 검색에서 반례와 풀이법 등을 찾아 보다가 한 귀인 분을 만나게 된다..
질문 - 동적계획법 optimal substructure 가 이해가 안돼요ㅜ
(이 문제 해결에 애를 먹고 있는 분이 계시다면 읽어 보시면 도움이 될 것 같습니다!)
답변 내용을 요약해보면 아래와 같다.
1, 2, 3, ... n번째 잔의 포도주의 양을 각각 p1, p2, p3, ... pn 이라 하고, i번째 잔까지 마신다 했을 때 마실 수 있는 포도주의 양의 최댓값의 배열을 DP[i] 라 했을 때, DP[i] 는 아래의 3가지 경우 중 최댓값으로 결정된다.
- DP[i] = DP[i-2] + pi → i-2번째 잔까지 마신 후 i번째 잔을 마시는 경우
- DP[i] = DP[i-3] + pi-1 + pi → i-3번째 잔까지 마신 후 연속으로 두 잔(i-1, i)을 마시는 경우
- DP[i] = DP[i-1] → i-1번째 잔까지 마신 후 i번째는 건너뛰는 경우
또한 위 질문을 읽어보면서 개인적으로 Optimal substructure 에 대해 한층 더 깊은 이해를 할 수 있었다고 생각한다. (답변 달아주신 고수님께 다시 한 번 감사 인사를 드립니다 .!!!)
항상 DP[i]에 DP[i-1]이 이용되는 것은 아니다. 이 문제의 경우처럼 상황에 따라서는 i-1, i-2, i-3번째, 혹은 더 이전의 최적해를 이용해서 DP[i]를 구해야 하는 문제가 있을 수도 있는 것이다. 고정관념에서 벗어나자!
#include <iostream>
using namespace std;
int wine[10001] = {0, };
int DP[10001];
int max3(int a, int b, int c) {
if (a > b) {
if (a > c) return a; // a > b && a > c
else return c; // c > a > b
}
else { // b > a
if (b > c) return b; // b > a && b > c
else return c; // c > b > a
}
}
int main(void) {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>wine[i];
}
DP[0] = 0;
DP[1] = wine[1];
DP[2] = wine[1] + wine[2];
for(int i=3; i<=n; i++) {
int a = DP[i-2] + wine[i];
int b = DP[i-3] + wine[i-1] + wine[i];
int c = DP[i-1];
DP[i] = max3(a, b, c);
}
cout<<DP[n]<<endl;
return 0;
}