알고리즘 풀이 - 백준 2156(포도주 시식, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 N개의 일렬로 놓인 포도주가 각각 양이 같거나 다르게 놓여 있을 때 연속하여 3잔을 마시지 않고 가장 많이 마실 수 있는 경우의 양을 구하는 문제이다.

 

 

2. 풀이

 

이 문제는 기본적으로 DP 문제이다. 

 

포도주를 마시는 경우의 수는 어떤 것일까? 연속해서 3잔을 마시지 말아야 하기 때문에 이전에 어디를 마셨던 것인가를 알고 있어야 한다.

즉, 좌측 부터 마신다는 가정을 할 때, 어디를 마셨는지를 알고 있어야 한다는 의미이다. 그것을 하나의 State라고 볼 수 있을 것이다.

 

포도주가 총 6잔이 놓여 있다고 가정해보자. 중간에 있는 내역들을 통해 어떤걸 마시는 경우가 있을 지 추측해보자.

만약 4번 포도주를 반드시 마신다는 가정을 한다면! 아래와 같은 두 가지의 경우가 있을 수 있다.

 

1번 포도주	2번 포도주	3번 포도주	4번 포도주	5번 포도주	6번 포도주
10	2	7	6	4	20

 

1번 포도주	2번 포도주	3번 포도주	4번 포도주	5번 포도주	6번 포도주
10	2	7	6	4	20

 

위의 표에서 파랗게 칠한 2번 혹은 1,3번 포도주를 먹는 경우를 알아야 한다. 아래와 같이 설명할 수 있다.

① 2번 포도주를 먹는다면 3번 포도주는 먹을 수 없으니, 2번 포도주까지 먹었을 때의 최대값에 4번 포도주를 마신 경우
② 3번 포도주를 먹는다면 2번 포도주는 먹을 수 없으니, 1번 포도주까지 먹었을 때의 최대값에 3+4번 포도주는 마신 경우

 

즉, 포도주의 개수에 따라 이전의 포도주를 먹었을 때의 상태값을 State로 지정하여 1차원의 배열로 저장하면 된다.

 

다만, 여기서 하나 유념해야 한다. 위에서 4번 포도주를 반드시 마신다는 가정에서는 최대값을 위를 통해서 구할 수 있지만, 반드시 그래야 할까?

3번 포도주까지 먹은 경우 중 최대값이 있을 수도 있다. 즉, 4번을 먹지 않고 1,3번 혹은 2,3번을 먹은 경우가 더 큰 값일 수 있다.

그래서 최대값을 온전하게 구하기 위해서는 그 경우 또한 체크를 해야 한다.

 

 

여기서 State의 정의를 알아보자. State를 저장하는 배열은 DP[]라고 하자.
정의 : DP[N] = N번째 포도주를 마셨을 때, 마실 수 있는 최대 포도주의 양

 

그러면 점화식과 기저 상태를 알아보자.(참고로 원래 포도주의 양을 저장한 배열은 arr[]이라고 가정)

점화식 : DP[N] = MAX(MAX(DP[N-3] + arr[N-1] + arr[N], DP[N-2] + arr[N]), DP[N-1])
위에서 보면 MAX를 두 번 썼고, DP[N-1]과도 비교를 하고 있다. 이를 빼먹어선 안된다.

기저 상태는 N=1, N=2일 때다. 왜냐면 N-3까지 점화식에서 쓰기 때문(index로는 0이겠지만 여기서는 1로 생각)
기저 상태 : DP[1] = arr[1], DP[2] = arr[1] + arr[2]

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] dp;
    static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        
        dp = new int[10001];
        arr = new int[10001];
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
            
            if(i == 0){
                dp[i] = arr[i];
                continue;
            } else if(i == 1){
                dp[i] = arr[i] + arr[i-1];
            } else if(i == 2){
                dp[i] = Math.max(dp[i-2], arr[i-1]) + arr[i];
            } else {
                dp[i] = Math.max(dp[i-3] + arr[i-1], dp[i-2]) + arr[i];
            }
            
            // N-1번째까지가 더 큰 경우도 비교해야!
            dp[i] = Math.max(dp[i-1], dp[i]);
        }
        bw.write(String.valueOf(dp[N-1]));
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] dp;
    static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        
        dp = new int[10001];
        arr = new int[10001];
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        topDown(N-1);
        bw.write(String.valueOf(dp[N-1]) + "\n");
        bw.flush();
        br.close();
    }
    
    // Top-down 방식, 행을 y, 열을 x로 표현하자
    public static int topDown(int n){
        if(n == 0) return dp[n] = arr[n];
        if(n == 1) return dp[n] = arr[n] + arr[n-1];
        if(n == 2) return dp[n] = Math.max(Math.max(arr[n-1], arr[n-2]) + arr[n], topDown(n-1));
        if(dp[n] > 0) return dp[n]; // 기존의 값이 있는 경우
        
        dp[n] = Math.max(Math.max(topDown(n-2), topDown(n-3) + arr[n-1]) + arr[n], topDown(n-1));
        
        return dp[n];
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.