[백준] #2156 포도주 시식, DP

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

 

아래는 내가 처음에 작성한 코드이다. 근데 틀렸다...

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        int answer = 0;
        
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        dp[1] = arr[1];
        answer = dp[1];
        if (n >= 2) {
            dp[2] = arr[1] + arr[2];
            answer = Math.max(answer, dp[2]);
        }

        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 2] + arr[i],
                             dp[i - 3] + arr[i - 1] + arr[i]);
            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);
    }
}

 

 

우선 내가 사고했던 방식을 정리해보자면,

보자마자 계단 오르기 문제를 DP로 풀이했던게 생각났고, 그래서 비슷한 방식으로 접근했다.

계단 오르기 문제와 다른 점이라면,

계단 오르기 문제는 그 계단을 밟아야 그 계단에 쓰인 점수를 얻을 수 있고, 마지막 계단을 반드시 밟는 다는 내용이 있다.

 

 

포도주 시식 문제는 위와 같은 조건은 없지만 dp[i]를 그 포도주를 마실 때 최대로 마실 수 있는 포도주의 양이라고 내가 정의했다.

만약 i번째를 마시지 않는다면 dp[i]말고 dp[i - 1] 등에서 답을 도출해낼 수 있을 것이라 생각했다.

(어차피 최댓값을 찾는거고 dp[i]를 제외한 dp 배열의 값들에는 i번째 포도주를 마시지 않는 경우를 고려한 최댓값이 들어있을테니)

근데 틀린 답이라고 한다....

사실 아직도 이게 왜 틀린 사고인지 이해가 되지 않는다. (아시는 분 설명 부탁드려요... 이 사고가 안통하는 반례를 알고 싶다.)

GPT나 gemini한테 반례 들어달라고 물어봐도 아래처럼 우연히 맞는 케이스를 계속 내뱉는다,,

 

 

아직 납득은 안됐지만,,,, 

어쨋든 다른 방식을 찾아서 코드를 고쳐보았다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];  // dp[i]: i번째 잔까지 고려했을 때의 최댓값

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

        dp[1] = arr[1];
        if (n >= 2) dp[2] = arr[1] + arr[2];

        for (int i = 3; i < n + 1; i++) {
            // 아래의 dp[i - 1]은 현재 잔을 마시지 않는 경우
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
        }
        System.out.println(dp[n]);
    }
}

 

여기서의 dp[i]는 i번째 잔까지 중 규칙을 고려하여 마실 수 있는 포도주의 최댓값이다.

엄....솔직히 내 코드랑 다른 건 dp[i - 1]이랑 최댓값을 비교하냐, 아니면 지금까지 담은 것 중 최댓값과 비교하냐의 차이인 것 같은데....

정확히 내  첫 코드가 뭐가 틀린건지 잘 모르겠다!!!!

아시는 분 알려주시면 감사하겠습니다