[알고리즘] 백준 - 포도주 시식

백준 - 포도주 시식

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class baekjoon_2156 {

    static int[] arr;
    static int[] 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 + 10];
        dp = new int[n + 10]; //dp[i] = i번째까지 최대값

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

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

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

    }

    private static int solve(int i) {
        if (i == 1 || i == 2 || i == 3) {
            return dp[i];
        }
        if (dp[i] == 0) {
            dp[i] = Math.max(Math.max(solve(i-3) + arr[i-1] + arr[i], solve(i-2) + arr[i]), solve(i-1));
        }
        return dp[i];
    }
}

처음에는 dp[i] = i번째를 마셨을때 i번째까지 최대값이라고 했다가 틀렸었다. 1000, 1000, 1 같은 경우 세번째는 1001 밖에 되지 않는다. 이렇게 되면 맨 마지막에 최대값이 들어가있다고 장담할 수 없다.

처음 dp가 0으로 초기화 되어있고 solve 함수에서 if (dp[i] == 0) 조건을 걸어서 에러가 났다. dp[1]도 0이므로 dp[-2]까지 접근하려하기 때문이다. 따라서 기저 조건을 따로 분리했다.
12
0
0
0
0
0
0
0
0
0
0
0
0
반례에서 index 에러가 났다.

반례 모음

반례 1

7
100
100
1
1
1
100
100

반례 2

6
1000
1000
1
1
1000
1000

반례 3

12
0
0
0
0
0
0
0
0
0
0
0
0