챕터3-11. DP | 문제 풀이2 - (5) 백준 No.2156 : 포도주 시식

포도주 시식 문제

- https://www.acmicpc.net/problem/2156

문제요약

포도주가 일렬로 놓여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 한다.
1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속적으로 놓여 있는 3잔을 모두 마실 수는 없다.

해결 방법1 (2차원 배열)

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "A[1]~A[N] 즉, N개의 포도주가 있을 때 가장 최대로 마실 수 있는 양"
   D[N][S] = "N개의 포도주 잔이 있고, N번째 포도주 잔의 상태가 S일 때 가장 최대로 마실 수 있는 양"
   S는 3가지 상태일 수 있음

   S = 0 : N번째 포도주 잔을 0번 연속으로 먹은 상태인 경우(N-1번째가 어떤지 상관없이 ...X 인 경우)
   S = 1 : N번째 포도주 잔을 1번 연속으로 먹은 상태인 경우(..XO 인 경우)
   S = 2 : N번째 포도주 잔을 2번 연속으로 먹은 상태인 경우(..XOO 인 경우)

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

 

case 1) S = 0 : N번째 포도주 잔을 0번 연속으로 먹은 상태인 경우(N-1번째가 어떤지 상관없이 ...X 인 경우)
- N번째가 D[N][0] 상태이면 N-1번째에는 3가지 상태 모두 올 수 있기 때문에
- D[N][0] = max(D[N-1][0], D[N-1][1], D[N-1][2])

 

case 2) S = 1 : N번째 포도주 잔을 1번 연속으로 먹은 상태인 경우(..XO 인 경우)

- N번째가 D[N][1] 상태이면 N-1번째에는 D[N-1][0] 상태만 올 수 있기 때문에
- D[N][1] = D[N-1][0] + A[N]

 

case 3) S = 2 : N번째 포도주 잔을 2번 연속으로 먹은 상태인 경우(..XOO 인 경우)
- N번째가 D[N][2] 상태이면 N-1번째에는 D[N-1][1] 상태만 올 수 있기 때문에
- D[N][2] = D[N-1][1] + A[N]

 

따라서 점화식은 max(D[N][0], D[N][1], D[N][2])

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10001];
int d[10001][3];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    
    d[1][1] = arr[1];           // 1잔만 있을 경우 최대 값은 1잔을 마시는 것이므로.
    
    d[2][0] = arr[1];           // 2잔만 있을 경우 2번째 자리의 상태가 S = 0인 경우의 최대값.
    d[2][1] = arr[2];           // 2잔만 있을 경우 2번째 자리의 상태가 S = 1인 경우의 최대값.
    d[2][2] = arr[1] + arr[2];  // 2잔만 있을 경우 2번째 자리의 상태가 S = 2인 경우의 최대값.

    for (int i = 3; i <=n; i++)
    {
        d[i][0] = max(max(d[i-1][0], d[i-1][1]), d[i-1][2]);
        d[i][1] = d[i-1][0] + arr[i];
        d[i][2] = d[i-1][1] + arr[i];
    }
    
    cout << max(max(d[n][0], d[n][1]), d[n][2]) << "\n";
}

 

(2) 시간복잡도
= for 문의 반복 횟수 

= O(N)

해결 방법2 (1차원 배열)

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "A[1]~A[N] 즉, N개의 포도주가 있을 때 가장 최대로 마실 수 있는 양"

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

case 1) N번째 잔이 0번 연속마신 상태인 경우 (이전상태 상관없이...X)
- 마실 수 있는 포도주의 최대양 : D[N-1]

 

case 2) N번째 잔이 1번 연속마신 상태인 경우(.....XO)
- 마실 수 있는 포도주의 최대양 : D[N-2] + 0 + A[N]

 

case 3) N번째 잔이 2번 연속마신 상태인 경우(....XOO)
- 마실 수 있는 포도주의 최대양 : D[N-3] + 0 + A[N-1] + A[N]

 

따라서 점화식은 D[N] = max (D[N-1], D[N-2] + A[N], D[N-3]  + A[N-1] + A[N]) 

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10001];
int d[10001];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    
    d[1] = arr[1];           // 1잔이 있을 때 최대 값은 1잔을 마시는 것임
    d[2] = arr[1] + arr[2];  // 2잔이 있을 때 최대 값은 2잔을 모두 마시는 것임

    for (int i = 3; i <=n; i++)
        d[i] = max(max(d[i-1], d[i-2] + arr[i]), d[i-3] + arr[i-1] + arr[i]);
    
    cout << d[n] << "\n";
}

 

(2) 시간복잡도
= for 문의 반복 횟수 

= O(N)