BOJ 2156(포도주 시식)

📜 문제

문제링크
BOJ 2579(계단오르기)와 거의 비슷한 문제였다.

---

📖 풀이

연속된 3개의 포도주를 마시지 않으면서, 최대로 마실 수 있는 포도주의 양을 구해야 한다. 전형적인 Dynamic Programming 문제이다.

1. 공간복잡도

   1) n 개의 포도주를 저장할 배열
   2) 점화식 d 의 값들을 저장할 배열

n의 최대값은 10,000 개 이므로 메모리 제한은 걱정할 필요없다.

2. 시간복잡도

   1) d[i][0] 를 구하기 위해서 i-2 번의 반복연산 필요 O(N^2)
   2) d[i][1] 를 구하는 과정 O(N)
   3) 최대로 마실 수 있는 포도주의 양을 구하는 과정 O(N)

d[i][0] 를 구하는 과정에서 i-2번째까지의 최대값을 찾는 과정이 있기 때문에 시간복잡도는 O(N^2) 이 된다. 시간제한은 2초이기 때문에 10^8으로 충분히 가능하고, 또한 i = N 일 경우에, N-2 번으로 실제 시간복잡도는 O(N^2) 보다 작기 때문에 시간내에 통과가 가능하다.

---

🖥 코드

#include <iostream>
using namespace std;

int d[10002][2];
int arr[10002];
int n;

int main(void){

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)cin >> arr[i];
    
    //초기값 설정
    d[1][0] = arr[1];
    d[2][0] = arr[2];
    d[2][1] = arr[1] + arr[2];
    //점화식
    for(int i = 3; i <= n; i++){
        int max = 0;
        for(int j = 1; j <= i-2; j++)
            for(int k = 0; k < 2; k++)
                if(d[j][k] >= max)max = d[j][k];
        d[i][0] = max + arr[i];
        d[i][1] = d[i-1][0] + arr[i];
    }

    int max = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 2; j++){
            if(d[i][j] >= max)max = d[i][j];
            //cout << d[i][j] <<' ';
        }
        //cout <<'\n';
    }

    cout << max;

    return 0;
}

---

🔨 피드백

처음 문제를 읽고, 이전에 풀었던 계단 오르기와 유사하다고 생각해 바로 점화식을 설정했다.

d[i][0] = 연속되지 않고 i번째 포도주를 마셨을 때, 최대값
d[i][1] = i-1번째를 마시고, i번째를 마시는 경우, 최대값

수식으로 표현하면 아래와 같다.

d[i][0] = (d[1][] ~ d[i-2][]) 범위 최대값 + arr[i]
d[i][1] = d[i-1][0] + arr[i]

이렇게 점화식을 구성하고 d[1][0] ~ d[N][1] 까지 돌면서 최대값을 구하면 최대로 마실 수 있는 포도주의 양을 구할 수 있다.

---

🔥 점화식을 1차원으로 선언해도 문제를 해결할 수 있다.

d[i] = i 번째에 도착했을 때, 마실 수 있는 최대 와인의 양

이렇게 되면 i번째에 3개의 case를 생각해줘야 한다.

1) i 번째 와인을 마시지 않는 경우, d[i-1]
2) i 번째 와인을 마시고, i - 1 번째 와인을 마시지 않는 경우 d[i-2] + arr[i]
3) i 번째 와인을 마시고, i- 1 번째 와인도 마신 경우 d[i-3] + arr[i-1] + arr[i]

이렇게 d[i] = max( d[i-1], d[i-2] + arr[i], d[i-3] + arr[i-1] + arr[i]) 로 구현하면 처음에 구상한 풀이보다 공간복잡도나 시간복잡도에서 더 효율적으로 문제를 해결할 수 있다!!