[BOJ - JAVA] 2156 - 포도주 시식(DP)

# 주소

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

2156번: 포도주 시식

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.Scanner;

public class Main {
	
	static Integer[] dp;
	static int[] arr;
    
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		dp = new Integer[N + 1];
		arr = new int[N + 1];
		
		for(int i = 1; i < N + 1; i++) {
			arr[i] = in.nextInt();
		}
 
		dp[0] = 0;
		dp[1] = arr[1];
		
		if(N > 1) {
			dp[2] = arr[1] + arr[2];
		} 
		
		System.out.println(recur(N));
	}
	
	static int recur(int N) {
		
		if(dp[N] == null) {
			dp[N] = Math.max(Math.max(recur(N - 2), recur(N - 3) + arr[N - 1]) + arr[N], recur(N - 1));
		}
		
		return dp[N];
	}
}

재귀함수의 정석대로 풀어야 합니다. 

DP[N]이 null일 때만 함수를 시행하는 것을 알 수 있는데 이는 메모이제이션을 이용한 것으로서 처음에 dp를 생성할 때 int 타입이 아닌, Integer 타입으로 선언하면 객체의 값을 참조하지 않고 인덱스에 값이 있는지 여부를 판단하기 때문에 탐색 속도가 int타입으로 했을 때 보다 빠르다는 장점을 가지고 있습니다.

dp는 n부터 재귀함수를 실행하며 n값을 낮췄을 때 그 대소 관계를 각각 비교하여 가장 큰 값을 계속해서 재귀로 돌려주는 것이 핵심인데요.

dp[0]은 0, dp[1] = arr[1], dp[2] = arr[1] + arr[2]를 넣어줌으로서 n이 3보다 작을 때를 방지합니다.

핵심은 밑으로 내려가서 재귀함수 recur를 짤텐데요. 

여기서 핵심은 recur(n-2)와 recur(n-3) + arr(n-1) + arr(n)중 더 큰 값과 recur(n-1)를 비교함으로써 모든 경우의 수에 대비할 수 있습니다.

즉, recur(n-3) + arr(n-1) + arr(n)이 가장 큰 값이라면 이는 끝 원소 3개가 2 8 3을 예로 들었을 때 8 + 3이 선택될 것이라는 뜻이며 recur(n-3)을 다시 시행한다는 것을 의미합니다. 이 때 recur(n-3)을 실행한다는 것은 위로 올라가 recur함수에 n이 n-3일 때를 실행한다는 것이므로 recur(n-5)와 recur(n-6) + arr(n-4) + arr(n) 중 더 큰 값과 recur(n-4)를 비교한다는 뜻입니다. 이를 로직으로 다 구현하려면 상당히 복잡하지만 자바에서는 재귀함수를 지원하기 때문에 단순한 명령어만으로 3가지 경우의 수에 모두 대비할 수 있습니다.

 

감사합니다.