[BOJ] 백준 2156 - 포도주 시식 (자바)

DP.........

dp 문제

풀이

1. oox, oxo, xoo 의 경우가 존재한다.

 1-2. oox 의 경우 dp[i-1] 가 된다.

 1-3. oxo 의 경우 dp[i-2] + arr[i] 가 된다.

 1-4. xoo 의 경우 do[i-3] + arr[i-1] + arr[i] 가 된다.

2. 위의 3경우중 가장 큰 값을 선택하면 된다.

 dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i])) 라는 수식이 나온다.

3. 끝.

4. 아 여기서 N=1 일때와 2일때가 존재한다. 이때의 경우를 조건을 통해 잘 계산하도록 한다.

소스

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        }
        // 첫잔일 경우
        if (N >= 1) {
            dp[0] = arr[0];
        }
        // 두잔일 경우
        if (N >= 2) {
            dp[1] = arr[0] + arr[1];
        }
        // 세잔일 경우
        if (N >= 3) {
            dp[2] = Math.max(dp[1], Math.max(dp[0] + arr[2], arr[1] + arr[2]));
        }
        for (int i = 3; i < N; i++) {
            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 - 1]);
    }
}