[백준] 2156번 : 포도주 시식 - JAVA [자바]

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

---

• 문제

 

 

 

 

만약 백준 카테고리에서 동적계획법을 차례대로 풀어왔다면 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

아마 동적계획법1 카테고리 문제를 차례대로 풀어왔다면 2579번 문제인 '계단 오르기'랑 매우 유사하다는 것을 느끼셨을 것이다. 이 문제를 풀기에 앞서 혹여 기억이 안나거나 아직 풀어보지 못한 분은 계단 오르기 문제를 보고 오시는 것을 추천드린다.

 

필자도 이에 대해 포스팅 했으니 아래 포스팅을 참고하시면 좋겠다.

 

st-lab.tistory.com/132

[백준] 2579번 : 계단 오르기 - JAVA [자바]

 

 

위 문제랑 거의 유사하다. 연속된 것을 선택할 때 두 번을 초과할 수 없다 또한 선택한 것들의 합이 최댓값이 되도록 해야한다.. 다만 다른 점이 있다면, 계단 오르기 문제는 '마지막 계단은 반드시 밟아야 한다'는 점이고 이번 포도주 시식은 그런 조건이 없다.

 

그럼 이 차이점은 무엇을 의미할까?

 

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

 

쉽게 생각하면 이렇다

 

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

 

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

10, 30, 1 → 누적합 : 41

 

<위 조건이 없는 경우>

25, 30 → 누적합 : 55

 

차이가 보이는가? 아마 이번 문제의 정답비율이 생각보다 낮은 이유가 이러한 조건을 제대로 인지하지 못한 채 풀어서 그러지 않을까... 이 것만 제대로 알아도 쉽게 풀 수 있을 것이다.

 

 

 

그럼 본격적으로 알고리즘 부분으로 넘어가보자.  두 가지 방식으로 설명을 드리고자 한다. Top-Down방식으로 재귀를 통해 구현해보는 것과, Bottom-Up방식으로 반복문을 통해 구현해보고자 한다. 앞서 링크한 포스팅을 보셨다면 알고리즘을 알 수 있겠지만, 보지 않으신 분들도 있을 것 같기에 내용이 일부 중복되어도 양해바란다. 

 

 

 

[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]

 

그럼 반복문으로, 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까지 순차적으로 쌓아가면서 풀어나가는 것이 특징이다.

 

 

더욱 자세한 내용은 코드를 보면서 설명해주겠다.

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

여타 포스팅과 다를 것 없이 입력방법에 따른 각각의 알고리즘에 대해 성능비교를 해보고자 한다. 입력방법은 Scanner와 BufferedReader, 알고리즘은 재귀(Top-Down)와 반복문(Bottom-Up)을 통하여 보여줄 것이다. 즉, 다음과 같이 진행할 것이다.

 

 

1 . Scanner + Top-Down

2. BufferedReader + Top-Down

3 . Scanner + Bottom-Up

4. BufferedReader + Bottom-Up

 

 

 

 

---

• 풀이

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

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

어떤 분이 재귀 위주로 풀어내서 어렵다고 하는데 필자도 알고는 있다. 다만, 대부분 타 블로그나 제출자 대부분이 bottom-up방식으로 풀어서 top-down방식을 접하기가 힘들다고 봤다. 그래서 여러 풀이법을 알려주고자 하는 의도가 크기도 하고,, 또한 점화식만 찾아내면 쉽게 풀 수 있는 방법 중 하나이기 때문에 여러분들도 이런 부분에 좀 더 익숙해지면 좋지 않을까 싶어 재귀 위주로 푼다.

 

무엇보다 코드가 깔끔해 보인다.

 

 

---

- 방법 2 : [BufferedReader + Top-Down]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 알고리즘은 그대로다.

 

 

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

public class Main {
	
	static Integer[] dp;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		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];
		
		/*
		 *  (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];
	}
}

 

 

 

 

 

 

---

- 방법 3 : [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 이라고 해주어야 한다.)

 

 

 

---

- 방법 4 : [BufferedReader + Bottom-Up]

 

 

 

마찬가지로 Scanner 대신 BufferedReader 을 사용한 방식이다.

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int[] arr = new int[N + 1];
		int[] dp = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

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

}

 

 

 

크게 어려울 것은 없을 것이다. 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 22189820  -  방법 4 : BufferedReader + Bottom-Up

채점 번호 : 22189812  -  방법 3 : Scanner + Bottom-Up

채점 번호 : 22189803  -  방법 2 : BufferedReader + Top-Down

채점 번호 : 22189799  -  방법 1 : Scanner + Top-Down

 

 

 

알고리즘 차이는 거의 없는 듯 하다..

---

• 정리

 

 

오늘은 크게 설명할 부분은 없었다. 적어도 필자가 보고 오라는 계단 오르기 문제를 제대로 이해했다면 이 번 문제는 더더욱이 쉬웠을 것이다. 혹여 모르거나 이해가 되지 않다면 꼭 댓글 남겨주셨으면 한다. 그래야 필자도 좀 더 보완하고 다른 분들에게도 도움될 수 있으니...

 

 

여담)

요즘 다시 코로나가 대유행하며 서울 및 수도권은 2.5단계 거리두기를 하고 있다. 이 포스팅을 보는 분들 연령층이 정확히 어떻게 되는지는 모르겠다만.. 필자도 그렇고 아마 많은 분들이 다양한 방면에서 우울감, 무력함과 더불어 많이 힘드시리라 본다. 필자도 거의 새벽 2시~4시까지 깨어있는 경우가 많은데 어제 밖을 보니 11시지만 11시 같지 않고 새벽 4시 무렵을 보는 듯한 기분이였다.. 정말 한산했고 반쯤 유령도시가 된 것 같은 느낌과 필자가 하는 모든 모임들도 중단... 그러다보니 사실상 반강제로 생활패턴이 낮으로 돌아와버린 것 같다. (저녁 7시경 포스팅을 올리다니.. )

 

아무쪼록 이런 와중에도 필자의 포스팅을 봐주시고 고맙다는 댓글을 남겨주시는 모든 분들께 감사할따름이다. 모두 코로나 조심하고 건강하시길 바란다.