(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 2156번 포도주 시식(실버 1)

이번 문제는 n개 만큼의 포도주가 있을때, 연속으로 3잔을 마실 수 없는 경우 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하는 문제이다.

저번에 풀었던 계단 문제와 크게 다르지 않으므로 간단하게 풀어 낼 수 있었다.

그럼 어떻게 풀었는지 살펴보자.

---

 

규칙은 간단하다!

규칙은 이전 계단 문제와 비슷하다.

3잔을 연달아 마실수 없으므로 결국 비교해야하는 것은 -3 인덱스에 -1 인덱스에 해당하는 값을 더한 값과 -2된 값중 큰것을 자기 인덱스의 값과 더하면 된다.

테이블로 살펴보자.

0	1	2	3	4	5	6
0	6	10	13	9	8	1
0	6	16

초기값을 셋팅해주면 (0번째 인덱스는 무조건 0이라고 가정한다.) 2번째 인덱스의 값은 무조건 1번 인덱스의 값에 자기 값을 더한 값이 된다.

그러면 3번째 인덱스의 값인 13을 계산해보자.

3잔을 연달아 마실수 없으므로 우리는 0번 인덱스 값에 직전 인덱스의 숫자인 10을 더한 값과 3-2를 하여 1번 인덱스의 값인 6중 큰것을 13과 더하면 된다.

따라서 3번째 인덱스의 값은 다음과 같이 될것이다.

0	1	2	3	4	5	6
0	6	10	13	9	8	1
0	6	16	23

이런식으로 쭉 풀어나가면 다음과 같이 테이블이 채워진다.

0	1	2	3	4	5	6
0	6	10	13	9	8	1
0	6	16	23	28	33	32

중요한 것이 하나 더 있는데 이전 계단 문제는 반드시 마지막 인덱스를 밟아야 했지만 이번 문제는 마지막이 꼭 들어가야 한다는 조건이 없다.

따라서, 최종 값을 구하기 위해서는 위의 계산된 값을 -1 인덱스의 값과 비교하여 더큰 값을 가져와야지 최종 값을 가져올 수 있는 것.

그럼 코드로 구현해 보자.

---

import java.io.*;
import java.util.*;

class Main{
    public static int n,result;
    public static int[] arr;
    public static Integer[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        dp = new Integer[n+1];
        result = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[0] = 0;
        dp[1] = arr[1];
        if (n > 1) {
            dp[2] = arr[1] + arr[2];
        }
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(Math.max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i], dp[i - 1]);
        }
        System.out.println(dp[n]);
    }

}

가장 중요한 것은 이부분인데.

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

보면 알수 있지만 -3 인덱스에 이전 숫자를 더한값과 -2 인덱스의 값중 큰것을 가져와 자신과 더한다.

그 후 -1 인덱스의 값과 비교하여 더 큰값을 가져오면 최종적으로 마지막 값이 가장 큰 값이 되기 때문에 dp[n]을 출력하여 가장 큰 값을 가져올 수 있게된다.