[Java] 2156번: 포도주 시식 Silver 1

문제 링크

이제 무조건 코테를 칠 때처럼 종이(아이패드 ㅎ)에 다가 적으면서 푼다!

처음보자마자 계단 오르기가 생각이 나서 바로 점화식을 세울 수 있었다!!

그러나.. 2%에서 틀리고 마는데,, 그 이유는 내가 정의한 DP[i]는 i번 째 포도주를 마셨을 때의 최댓값이 때문이다..

즉, arr[i] 더한 값을 저장하기 때문에 무조건 i번 째 포도주를 마신다고 가정한 것이다..!
물론 이러면 그냥 최종적으로 for을 통해서 dp 배열을 한 바퀴 돈 다음에 그 중에서 최댓값을 출력하면 되지 않을까도 싶었지만, 그냥 안전하게 Max를 한 번 더 걸어주었다.

즉, 이제는 dp[i]를 i번 째까지 마실 수 있을 때의 최댓값으로 재정의한 것이다!

아 그리고 초기값 설정에 주의하자!!

예를 들어
1 2 3 이렇게 포도주가 있을 때 가능한 케이스는, 1 + 2, 1 + 3, 2 + 3 이렇게 총 세 개다!
별 거 아닌 거 같지만 이거 때문에 틀리는 경우도 꽤 있을테니 조심하자!

정답

import java.io.*;

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

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 배열 생성
        int[] arr = new int[N];
        int[] dp = new int[N];

        // 배열 입력 받기
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // DP
        if (N == 1) System.out.println(arr[0]);
        else if (N == 2) System.out.println(arr[0] + arr[1]);
        else if (N == 3) System.out.println(Math.max(arr[0] + arr[2], Math.max(arr[0] + arr[1], arr[1] + arr[2])));
        else {
            dp[0] = arr[0];
            dp[1] = arr[0] + arr[1];
            dp[2] = Math.max(arr[0] + arr[2], Math.max(dp[1], arr[1] + arr[2]));

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

            System.out.println(dp[N-1]);
        }
    }
}