백준 #2156. 포도주 시식

허찬·2022년 3월 7일
0

BOJ PS

목록 보기
3/9

백준 #2156. 포도주 시식

정리

이 문제를 풀 때, 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;
}
profile
나 허찬

0개의 댓글