[2156번] 포도주 시식 JAVA☕

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

2156번: 포도주 시식

알고리즘 [접근 방법]

https://linerate.tistory.com/31

[2579번] 계단 오르기 JAVA☕

위 문제와 거의 유사하지만 계단 오르기 문제는 '마지막 계단은 반드시 밟아야 한다'는 조건이 붙어 있기 때문에 포도주 시식 문제와는 차이점이 있다.

 '반드시 마지막 계단을 밟는다'는 의미는 결국 마지막 계단에 대한 경우의 수들의 누적합 중 최댓값이다. 즉, 이전 계단이 마지막 계단보다 누적합이 컸다고 하더라도 마지막 계단을 밟을 수 없다면 그 값은 위 조건에 위배되어 정답이 아니다. 반면에 포도주 시식은 그런 조건이 없다. 즉, 마지막 와인잔이 선택 될 때가 최대 누적합일수도, 또는 그 이전 와인잔까지 선택이 최대 누적합일 수도 있다.

쉽게 생각하자면,

 

10,25,30,1 이 차례대로 있고, 2개를 초과하여 연속으로 뽑을 수 없을 떄 마지막 숫자를 반드시 거쳐야 하는 경우와 그런 조건이 없는 경우 누적 합의 최대값은 다음과 같이 달라진다.

 

<마지막 숫자(1)를 반드시 거쳐야 하는 경우>

10,30,1 -> 누적합: 41

 

<위 조건이 없는 경우>

25,30 -> 누적합:55

---

[Top-Down]

먼저, N번째 값을 선택할 때 단순히 (N-1)번째 값을 선택할 경우 N-1 에서는 또 N-1의 -1, 즉 (N-2), 이런식으로 모든 값을 선택해버리는 문제가 발생한다. 즉, 우리는 호출해 줄 때 비연속적인 값을 탐색해나가는 방법이 필요하다. 그렇기 때문에 N번째 값에 대하여 (N-2)번째 값과 (N-3)번째 값을 탐색해줄 필요가 있다. 그리고 N-3의 경우 해당 재귀호출이 끝났을 경우 그에대한 값의 N-1값을 더해주는 방식으로 풀어나가야 한다. 

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

메모이제이션을 하는 배열이 dp라고 할 때 해당 N이 탐색하지 않았던 인덱스였다면 N-2를 재귀 호출 한 것과(비연속), N-3을 재귀호출 한 값의 N-1번째의 와인잔을 합한 값 중 큰 것을 선택한 뒤 현재 와인잔의 값과 합해준다. 방금도 말했지만 (N-1)까지 N-1에 대한 누적합과 N-3에 대한 누적합이 더해지는 것이므로 우리가 원했던 값이 나오지 않는다. 

 

그리고 포도주 시식에서 가장 큰 문제점인 어떤 것이 최댓값이냐를 풀어내야 한다. 왜냐하면 앞선 반례에서도 보여주었듯이 마지막 dp의 값이 항상 최댓값을 보장하는 것이 아니기 때문이다. 그렇기 때문에 답은 N-1 을 넘긴 재귀호출의 값과도 비교하는 것이다. 즉, N-1 번째 누적합과 큰 것 중 하나를 선택하여 dp를 갱신하는 것이다.

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];
}

recur(N-2) 와 recur(N-3) + arr[N-1] 중 큰 값이 반환되었을 때, 이 값을 이전 N인 recur(N-1)과 '비교'하여 dp[N]의 최댓값을 갱신하는 것이다. (비교와 더하는 것은 완전히 다르다.)

결과적으로 두 변수 중 큰 값이 dp[N]을 갱신시키는 것이다. 이렇게 갱신시키면 각 노드는 이전의 최댓값과 비교하게 되며 조합 가능한 것 중 최댓값만을 저장하게 되는 것이다.

 

[Bottom-Up]

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]));
}

(i가 3부터 시작하는 이유는 dp[i - 3]에서 인덱스 참조가 벗어날 수 있기 때문이다.)

Top-Down에서 썼던 점화식과 크게 차이가 안난다. 다만 Bottom-Up은 말 그래도 아래(작은 것)부터 위(큰 것)로 풀어나가는 방식이기다. 즉, i = 3부터 N까지 순차적으로 쌓아가면서 풀어나가는 것이 특징이다.

---

풀이 및 코드

- 방법 1 : [Scanner + Top-Down]

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];
		
		/*
		 *  (N이 1로 주어질 수 있으므로 이럴 때를 위해 조건식을 달아둔다.
		 *  또한 dp[2]는 어떤 경우에도 첫 번째와 두 번째를 합한 것이 최댓값이다. 
		 */
		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];
	}
}

- 방법 2 : [Scanner + Bottom-Up]

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
 
		int[] arr = new int[N + 1];
		int[] dp = new int[N + 1];
 
		for (int i = 1; i <= N; i++) {
			arr[i] = in.nextInt();
		}
 
		dp[1] = arr[1];
		if (N > 1) {
			dp[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]);
	}
 
}

위의 Top-Down방식과 마찬가지로 dp[1], dp[2]를 각각 arr[1]과 arr[1] + arr[2]로 초기화 해주어야 한다. (dp[0]은 int[]배열로 디폴트값이 0으로 초기화되어있어서 따로 안해줬다. 다만 Top-Down에서는 Integer[] 배열을 썼기 때문에 dp[0] = 0 이라고 해주어야 한다.)