2156: 포도주 시식 (DP)

풀이

dp를 처음 접해본 문제!

3잔을 연속으로 마실 수 없기 때문에 그때의 max값의 점화식을 구성해보면 된다.

6, 10, 13, 9, 8, 1이 차례로 들어올때

첫번째 6이 들어오면 dp[0]은 첫번째 (6)

두번째 10이 들어오면 dp[1]은 첫번째 + 두번째 (10 + 6)

세번째 13이 들어오면 dp[2]는 첫번째 + 두번째, 두번째 + 세번째, 첫번째 + 세번째 중에 가장 큰 것!

네번째 이후로 max는 그 전에 구했던 dp[i-1]과 dp[i - 2] + arr[i], dp[i - 3] + arr [i] + arr[i - 1]중에 큰 값이 된다.

코드

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		int[] dp = new int[N];

		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}

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

		int max = 0;
		for (int i = 0; i < N; i++) {
			max = Math.max(dp[i], max);
		}

		System.out.println(max);
	}
}