포도주 시식 - 백준 2156 (Java)

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

 

처음 풀이

맨 처음 문제를 읽고는 DFS 쪽으로 접근해볼까 했는데 조건이 포도잔이 최대 10000개까지라서 안될 거라 생각했다.

그래서 dp쪽으로 한번 접근해봤다.

 

연속된 3개의 와인은 마실 수 없다

 

이 조건을 어떻게 dp 풀이 방식에 적용할 수 있을까 고민했다.

 

dp[x] 는 x번째 와인까지의 최댓값인데 이를 3가지 경우로 나눠서 각각 dp[x][0], dp[x][1], dp[x][2]에 해당 값을 저장한다. 

 

dp[ x ][ 0 ] 

-> x번째까지 연속된 와인이 0개인 경우의 최댓값, 즉 x번째 와인을 선택하지 않은 경우

-> dp[x][0] = dp[x-1][0], dp[x-1][1], dp[x-1][2] 중에 최댓값이 된다.

 

dp[ x ][ 1 ]

-> x번째까지 연속된 와인이 1개인 경우의 최댓값, 즉 x-1번째 와인은 선택하지 않고, x번째 와인을 선택한 경우

-> dp[x][1] = dp[x-1][0] (x-1번째 와인을 선택하지 않은 경우) + x번째 와인의 양

 

dp[ x ] [ 2 ]

-> x번째까지 연속된 와인이 2개인 경우의 최댓값, 즉 x-1번째 와인을 선택하고, x번째 와인까지 선택한 경우

-> dp[x][2] = dp[x-1][1] (x-1번째 와인까지 선택해서 연속된 와인이 1개인 경우) + x번째 와인의 양

 

 

위 내용을 코드로 옮기면 다음과 같다.

 

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    //전체 와인잔 개수
    int totalCnt = Integer.parseInt(bf.readLine());
    //와인 양을 저장할 배열
    int[] glassArr = new int[totalCnt+1];

    for (int i = 1; i <= totalCnt; i++) {
        glassArr[i] = Integer.parseInt(bf.readLine());
    }//for end

    //중간값 저장할 dp 배열
    int dp[][] = new int[totalCnt+1][3];

    //3가지 경우에 대한 계산
    for (int i = 1; i <= totalCnt; i++) {
        dp[i][0] = maxOfThree(dp[i-1][0], dp[i-1][1], dp[i-1][2]);
        dp[i][1] = dp[i-1][0] + glassArr[i];
        dp[i][2] = dp[i-1][1] + glassArr[i];
    }//for end

    //최종적으로 dp[마지막 와인]에서의 3가지 경우 중 최댓값을 출력
    int max = maxOfThree(dp[totalCnt][0], dp[totalCnt][1], dp[totalCnt][2]);

    System.out.println(max);
}

//3가지 숫자 중 최댓값 리턴하는 메소드
public static int maxOfThree(int a, int b, int c) {
    return Math.max(a, Math.max(b, c));
}

 

 

dp문제만 만나면 잘 못 풀었는데 이번에 다른 풀이 안 보고 혼자 dp로 접근해서 끝까지 풀었다.

좀 더 수월하게 풀 수 있도록 더 많이 연습해야겠다.