[백준] 포도주 시식

문제는 다음 링크를 통해 볼 수 있다.

2156번: 포도주 시식

 

문제 풀이

---

이번 문제는 DP 문제이다. 문제에서 주어진 조건은 다음과 같다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

이번 문제에서 중요한 조건은 바로 2번 조건이다. 연속으로 3잔을 마실 수 없기 때문에 이 부분을 고려해야 한다.

먼저 와인이 1잔이 있을 때를 생각해보자. 와인이 1잔만 있다면 한잔을 마시는 것이 최대로 많이 마시는 것이다.

와인이 2잔이라면 2잔 모두 마시는 것이 최대로 많이 마시는 것이다.

 문제는 3잔부터이다. 3잔은 연속으로 마실 수 없기 때문에 어떤 잔을 마실지 선택해야 한다. 잔을 선택하는 경우를 O, 선택하지 않는 경우를 X라고 한다면 3잔을 선택하는 방법은 다음과 같다.

1. XOO
2. OXO
3. XXO
4. OOX
5. XOX
6. OXX
7. XXX

위 케이스에서 가장 마지막 잔이 N이라고 할 때, N -3번째 잔에 도달했을 때 마실 수 있는 포도주의 최대량을 DP를 이용해 기록한다면 일반화된 식을 세울 수 있다.

먼저 첫번째 케이스다. 첫번째 케이스의 경우 식을 다음과 같이 세울 수 있다.

DP[N] = DP[N - 3] + glasses[N - 1] + glasses[N]

N = 5라면 (2번째 잔까지 도달했을 때 최대량) + (4번째잔) + (5번째 잔)이 되는 것이다.

 

다음은 2번, 3번 케이스이다. 2번 3번 케이스의 공통점이 보이는가? 바로 마지막 잔은 먹고 그 전 잔은 먹지 않는다는 것이다. 식을 세우면 다음과 같다.

DP[N] = DP[N - 2]  + glasses[N]

여기서 왜 DP[N - 2]를 쓰는지 궁금할 수 있다. 먼저 DP[N - 3]을 이용해서 두 케이스의 식을 세워보면 다음과 같다.

2번 케이스: DP[N] = DP[N - 3] + glasses[N - 2] + glasses[N]

3번 케이스: DP[N] = DP[N - 3]                           + glasses[N]

DP[N - 2]는 N - 2번 째 잔에 도달했을 때 최대량이다. 즉 DP[N - 3] + glasses[ N - 2 ]와 DP[N - 3] 중 최대값이 DP[N - 2]이다. 그렇기에 2번 케이스와 3번 케이스에서 DP[N - 2]로 치환할 수 있는 것이다.

 

4, 5, 6, 7번 케이스도 마지막 잔만 먹지 않는다는 공통점을 이용하여 위와 같은 방식으로 계산을 해보면 다음과 같은 식을 세울 수 있다.

DP[N] = DP[N - 1]

 

위 3가지 식을 비교하여 가장 큰값을 DP[N]에 넣어주면 그것이 바로 N번 째 잔에서 마실 수 있는 가장 최대량이 된다.

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] glasses = new int[N + 2];
        int[] DP = new int[N + 2];

        for (int i = 1; i <= N; i++) {
            glasses[i] = Integer.parseInt(br.readLine());
        }

        DP[1] = glasses[1];
        DP[2] = glasses[1] + glasses[2];



        for (int i = 3; i <= N; i++) {

            int max = Math.max(DP[i - 2] + glasses[i], DP[i - 3] + glasses[i - 1] + glasses[i]);
            DP[i] = Math.max(max, DP[i - 1]);
        }

        System.out.println(DP[N]);
    }
}

 

주의할 점은 배열의 크기이다. DP를 이용하기 위해선 최소 2개 이상의 배열 공간을 확보하거나 따로 예외 처리를 해줘야 입력이 1, 2가 들어왔을 때 처리가 가능하다.