[백준] 동적계획법 (2156 : 포도주 시식)

문제

---

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

2156번: 포도주 시식

---

해설

---

해당 문제는 연속으로 3잔을 모두 마실 수 없다는 조건을 잘 생각해보아야 해결할 수 있는 문제였다.

예제 입력을 통해 해결방법을 알아보자.

	N = 1	N = 2	N = 3	N = 4	N = 5	N = 6
포도주	6	10	13	9	8	1
최대값	6	6+10 = 16	10+13 = 23	6 + 13 + 9 = 28	6 + 10 + 9 + 8 = 33	10 + 13 + 8 + 1 = 32
더한 인덱스	1	1,2	2,3	1,3,4	1,2,4,5	3,4,5,6

해당 표를 작성하며, 어떻게 해야 해당 위치까지의 합이 최대가 되는지를 알아보면 

아래 두가지 중 최대값을 선택하는 과정이 필요한 것을 알 수 있다.

• 현재 위치의 값 + 2개 전까지의 최대값
• 현재 위치의 값 + 이전 위치의 값 + 3개 전까지의 최대값

하지만 이렇게만 해서는 다른 예제를 해결할 수 없다.

ex) 6 100 100 1 1 100 100인 경우

위의 과정처럼 문제를 해결하면 결과는 아래의 표와 같이 나온다.

	N = 1	N = 2	N = 3	N = 4	N = 5	N = 6
포도주	100	100	1	1	100	100
최대값	100	100+100=200	100+1=101	100+100+1	100+100+1+100 = 301	100+1+100+100 = 301
더한 인덱스	1	1,2	1,3 or 2,3	1,2,4	1,2,4,5	1 or 2 ,3,5,6

사실 해당 예제에서 최대값은 아래와 같다.

	N = 1	N = 2	N = 3	N = 4	N = 5	N = 6
포도주	100	100	1	1	100	100
선택여부	O	O	X	X	O	O

100 + 100 +100 + 100 = 400이 나온다.

위에서 생각한 해결방법은 무조건 OXO. OXOO의 두가지 방법만 생각하기 때문에, OXXO를 처리하지 못한다.

이를 해결하기 위해서는 현재 포도주를 선택하지 않는 상황도 로직에 추가해야함을 의미한다.

이는, 이전까지의 와인의 합과 위의 조건을 비교해줌으로써 구현할 수 있었다.

코드는 아래와 같다.

sum[i] = Math.max(sum[i - 1], Math.max(sum[i - 2], sum[i - 3] + wine[i - 1]) + wine[i]);

앞의 예시처럼 N=3일때 N=3의 값인 1을 더하는 경우보다, N=1,2를 더하는 경우가 더 큰 것을 확인할 수 있다.(101 vs 200)

그렇다면, 이전까지의 포도주의 합인 200을 선택함으로써 N=3인 1을 마시지 않은 것으로 구현이 가능하다.

아래는 전체코드이다.

---

import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int wine[] = new int[N + 1];
        int sum[] = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }

        sum[1] = wine[1];
        if(N >= 2){
            sum[2] = wine[1] + wine[2];
        }
        for (int i = 3; i <= N; i++) {
            sum[i] = Math.max(sum[i - 1], Math.max(sum[i - 2], sum[i - 3] + wine[i - 1]) + wine[i]);
        }
        sb.append(sum[N]);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

반복문을 이용하는 Bottom-Up 방식이다.

---

1. 먼저 N이 1인경우와, 2인경우를 초기화시켜준다.
   여기서, 조건문을 N>=2인 경우 sum[2]를 초기화한 이유는 N=1인경우에 sum[2]는 존재하지 않는 인덱스이기 때문.
2. 반복문을 통해, 위의 로직을 수행한다.
3. 마지막 인덱스에 저장된 값이 포도주의 최대값이다.

---

결론

---

예제 입력을 해결해서 제출했는데 틀렸다고 해서 반례를 찾아보았는데,

생각지도 못한 방법으로 해결하는 사람들이 정말 신기한 것 같다.

어려웡

---