[백준] 2156번. 포도주 시식(JAVA)

문제

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

---

풀이(15분)

import java.io.*;
import java.util.*;
public class Main {

    static int[] arr;
    static Integer[] dp;

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

        int n  = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp = new Integer[n + 1];
        for(int i = 1; i<= n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        if(n == 1){
            System.out.println(arr[1]);
            return;
        }

        if(n == 2){
            System.out.println(arr[1] + arr[2]);
            return;
        }


        dp[0] = 0;
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];

        System.out.println(find(n));



    }

    public static int find(int N) {

        if(dp[N] == null) {
            dp[N] = Math.max(Math.max(find(N - 2), find(N - 3) + arr[N - 1]) + arr[N], find(N - 1));
        }

        return dp[N];
    }

}

 

이전에 풀었던 문제와 유사하여 쉽게 해결했다.

 

1. n이 1 or 2이면 이에 맞는 답을 출력하고 마무리한다.

2. dp 배열을 통해 해결한다.

 

dp의 구조는 다음과 같다. 내가 어떤 칸에 도달했을 때의 최고 값을 구하는 방법은 아래 규칙을 따른다.

1. 내 위치의 값을 더할 것인가?

2 - Y - 1 : n - 2번째 칸의 최대값과 자기 자신의 값을 더한다.

2 - Y - 2 : n - 3번째 칸의 값 + 자기 전의 칸 + 자기 자신의 값을 더한다. 

 

2 - N - 1: n-1번째 칸에 대한 dp값이 최고다.(자기 자신의 값은 건너 뛴다.)

 

이렇게 세개를 비교하는 것이다. 그럼 이때 들 수 있는 의문으로 아니 전 칸에 2개를 달고 온건지 한개를 달고 온건지 어떻게 아냐? 이다.

그렇다면 백준에서 제공하는 표준 예제를 따라가보자.

6
10
13
9
8
1

 

이 입력이 제공되었다.

dp[0] = 0, dp[1] = 6, dp[2] = 16으로 셋팅되었다. 이 때 dp[2]에 대해서는 dp[3]을 구할 때 자기 자신을 그대로 더하면 안 된다.(그럼 세개를 연속해서 마시는게 되기 때문이다.)

 

자 한번 살펴보자. 3번째 음료를 어떻게 할 것인가?

2 - Y - 1 : n - 2번째 칸의 최대값과 자기 자신의 값을 더한다.

2 - Y - 2 : n - 3번째 칸의 값 + 자기 전의 칸 + 자기 자신의 값을 더한다. 

 

2 - N - 1: n-1번째 칸에 대한 dp값이 최고다.(자기 자신의 값은 건너 뛴다.)

이 규칙을 따라 정리해보자.

 

2 - Y - 1: find(n-2) = null이 아니고 그러므로 dp[n-2] 즉 dp[1]이 반환된다. 거기에 자기 자신의 값인 arr[3] = 13을 더한다. 즉 19가 된다.

2 - Y - 2: find(n-3) + arr[2] + arr[3]  이다. dp[0] =0 이고 나머지 두 값을 더한 23이 반환된다.

2 - N - 1: find(n-1) : dp[2] = 16이 반환된다.

 

최종적으로 dp[3] = 23이 저장된다. 즉, 이미 자기 자신을 구할 때 이 전칸의 값에 대해서도 생각하며 최댓값을 구하는 로직이기에 3칸을 밟을 수 있는 문제가 해결된다는 것이다.