BOJ 백준 [2156] 포도주 시식

문제 내용

---

IDEA 1

무식하게 풀기

재귀함수를 통해 완전탐색을 하여 문제를 해결해보자.

#define MAX_WINE_CUP 10000
#define MAX_DRINK_CON 2
 
int wineAmount[10001] = { 0, };
int wineCupCount;
int totalDrink;
 
void drinkWine(int cupIndex, int drinkAmount, int continuous) {
    if (cupIndex > wineCupCount) {
        totalDrink = max(totalDrink, drinkAmount);
        return;
    }
 
    drinkWine(cupIndex + 1, drinkAmount, 0);
 
    if (continuous < MAX_DRINK_CON) {
        drinkWine(cupIndex + 1, drinkAmount + wineAmount[cupIndex], continuous + 1);
    }
}
 
int main() {
    
    ....
    
    totalDrink = 0;
    drinkWine(1, 0, 0);
    
    ....    
}

 위와 같이 문제를 해결할 경우 약 2^N( N = 와인잔의 갯수)의 시간이 소비된다.

이의 경우, N의 최댓값은 10000이므로 2^10000의 시간 즉 주어진 2초의 범위를 넘게 된다. 그래서 좀 더 시간을 줄일 수 있는 방법에 대해 모색해보아야한다.

 

---

IDEA 2

메모제이션 사용하기

 그렇다면, 앞의 연산을 가지고 활용할 수 있는 방법에 대해 고민해보자.

현재의 와인 위치 i에서 생길 수 있는 경우의 수는 아래와 같다.

1) i를 마시지않고 건너뛰는 경우

2) i-1과 i를 연속적으로 마시는 경우

3) i-1를 건너뛰고 i번째 포도주를 마시는 경우

위3개의 경우의 수를 고려하여 메모제이션해주면 O(N)의 시간으로 문제를 해결할 수 있다.

 

위의 점화식은 아래와 같이 세울 수 있다.

 

점화식

이를 활용하여 아래와 같이 문제를 해결하면 된다.

 

drinkAmout[1] = wineAmount[1];
drinkAmout[2] = wineAmount[1] + wineAmount[2];
 
for (int i = 3; i <= wineCupCount; i++) {
    drinkAmout[i] = max(drinkAmout[i - 2] + wineAmount[i],
                        max(drinkAmout[i - 1], drinkAmout[i - 3] + wineAmount[i - 1]+wineAmount[i]));
}