백준_2156 포도주 시식(JAVA) / DP

시간 & 메모리 제한

문제

입력 & 출력

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Back_2156 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [] cups = new int[N];
		int [] dp = new int[N];
		
		for (int i = 0; i < N; i++) {
			cups[i] = Integer.parseInt(br.readLine());
		}
		
		//>=로 해야 하는 이유 -> N의 갯수가 커져도 포함해야 하기 때문이다.
		// N이 1에서 3까지는 패턴이 동일하고 그 이후부터 변한다
		if(N>=1) {
			dp[0] = cups[0];
		}
		if(N>=2) {
			dp[1] = cups[0]+cups[1];
		}
		if(N>=3) {
			dp[2] = Math.max(dp[1], Math.max(cups[0] + cups[2], cups[1] + cups[2]));
		}			
		for (int i = 3; i < N; i++) {
			dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+cups[i], dp[i-3]+cups[i-1]+cups[i]));
		}
		
		System.out.println(dp[N-1]);
	}

}

 

dp가 1 과 2인 경우는 누구나 쉽게 구할 수 있습니다.

dp가 3인경우 그리고 4보다 큰경우는 아래의 그림을 보면 쉽게 이해가 될거 같습니다.