[자바] 백준 2156번 포도주 시식 2021-06-25

우선 문제 접근은 매우 쉬웠다 결국 틀렸지만ㅋㅋ,, 이전 포스트에서도 설명했듯, DP문제를 풀 때는 맨 마지막 항 N이 어떻게 구성될수 있는지 경우의 수를 나눠서 일반항을 구하는것과 구한 DP배열의 각 항이 무엇을 의미하는것을 정의하는게 제일 핵심이다.

 

 

1. 맨 마지막 항 N이 구성될 수 있는 경우는 3가지 이다.

내가 직접 그림을 그렸다.

 그런데 매우 특이한 점은, 맨 마지막항을 "무조건" 방문해야 한다는 조건이 없기에, 만약 2번 3번 경우보다 아예 해당 노드를 안방문하는 경우가 더 클 경우, 그냥 바로 전 항의 dp값을 현재의 dp값으로 할 수 있다는 것이다. 여기서 방문(마신다)는 것은 dp[i]의 값에 현재의 인덱스값 arr[i]를 더해주느냐 마느냐로 정할수 있다. dp[i]의 값을 구하는 식에서 arr[i](현재의 인덱스)를 더해주었다면, 현재 노드를 밟은 것이다.

 

잘 이해 안되면, 백준의 계단오르기 문제랑 비교 바란다. 나도 이런 조건때문에 한참 해매다 결국 다른 블로그 참고해서 겨우 해결했다..

 

2. 이렇게 일반항을 세웠으면, 각 DP값이 의미하는 바를 정의해보자.

난 "해당 인덱스만큼 포도주잔의 개수 존재할때, 먹을수 있는 최대의 값" 이라고 정의했다.

구체적으로 설명하자면, dp[3]=7 이라면 포도주잔이 3개있고, 먹을수 있는 최대양은 7이다.

 

그러므로 답을 출력할때는 dp배열중 가장 최대의 값을 출력해도 되고, 아니면 dp[n]항을 출력해도 무방하다. 왜냐하면 둘다 어짜피 최댓값일 테니까.

 

그리고 DP문제를 풀때, N항에 집중하기, DP인덱스의 의미정의, 초기값 설정.

이 세가지가 가장 중요하다고 나 스스로 밝혀냈는데, 초깃값 설정에서 굳이 해당노드를 안방문해도 된다는 것을 깜빡해서 또 해멨다... 역시 DP는 쉬우면서도 어렵다.

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int n=s.nextInt();
        int[] arr=new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=s.nextInt();

        }
        int[] dp=new int[n];
        if(n>=3) {

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

            dp[2]=Math.max(arr[0]+arr[2],arr[1]+arr[2]);
            dp[2]=Math.max(dp[1],dp[2]);//무조건 안밟아도 된다는 것을 간과함..
            //밑에서는 잘도 했는데 왜 초깃값에서 실수를..
        }
        else if(n==2){

            System.out.println(arr[0]+arr[1]);
            return;
        }
        else if(n==1){
            System.out.println(arr[0]);
            return;
        }
        for (int i = 3; i < arr.length; i++) {
            dp[i]=Math.max(dp[i-1],Math.max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]));
            //백준 계단오르기 문제랑의 차이점 살펴보기.->무조건 마지막 노드를 방문할 필요x,그렇기에
            //바로 이전 dp값이 다른 조건보다 크다면, 그대로 써도 됨.
        }
        int Max=Integer.MIN_VALUE;

        for(int a:dp){
            Max=a>Max?a:Max;
        }
        System.out.println(Max);




        }
    }