[JAVA] 백준 2156 - 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

🤔문제 접근

DP 문제인 포도주 시식 문제이다.

문제를 딱 봤을 때, 이전에 풀었던 같은 DP문제인 계단 오르기 문제가 생각났다.

연속해서 3개의 와인을 고를 수 없는 것이나 각 와인을 골랐을 때의 최대 양을 구하는 것이 계단 문제와 같았다.

하지만 다른 점이 있다면, 바로 마지막 와인이 정해져 있지 않다는 것이다.

계단 문제 같은 경우 마지막 계단을 반드시 밟아야 했지만 해당 문제는 그런 것이 없었기 때문에

최대 값을 비교하는 과정이 하나 더 필요했다. 해당 과정을 생각하는 것이 힘들었던 문제였다.

 

계단 문제와 동일하게 점화식을 세웠다.

static int find(int n){
    if(dp[n] == null){
        dp[n] = Math.max(find(n-3) + arr[n-1], find(n-2)) + arr[n]);
    }
    
    return dp[n];
}

 

관건은 항상 마지막 와인의 누적 합을 고르는 것이 최대 값 이냐는 것이었다.

따라서 최종적으로 n-1번째 누적 합과 n번째의 누적 합을 비교하도록 했다.

static int find(int n){
    if(dp[n] == null){
        dp[n] = Math.max(Math.max(find(n-3) + arr[n-1], find(n-2)) + arr[n]), find(n-1));
    }
    
    return dp[n];
}

 

🚨CODE

import java.io.*;
import java.util.*;

public class Main {
	static Integer[] dp;
	static int[] arr;
	public static void main(String[] args) throws Exception  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		dp = new Integer[n+1];
		arr = new int[n+1];
		
		for(int i = 1; i<n+1; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		dp[0] = 0;
		dp[1] = arr[1];
		
		if(n > 1) {
			dp[2] = arr[1] + arr[2];
		}
		
		System.out.println(find(n));
	}
	static int find(int n) {
		if(dp[n] == null)
			dp[n] = Math.max(Math.max(find(n-3) + arr[n-1], find(n-2)) + arr[n], find(n-1));
		
		return dp[n];
	}
}