[백준알고리즘-JAVA]2156번 풀이(포도주 시식) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 2156번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2156 (포도주 시식)

문제

효주는 포도주 시식회에 갔다. 그곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

 

포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

제한

시간제한 : 1 초 (추가 시간 없음)

입력 예시

6
6
10
13
9
8
1

출력 예시

33

성공 코드

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

public class Main {

	static int N ;
	static Integer[] dp;
	static int[] drink;
	static long max = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		dp = new Integer[N+1];
		drink = new int[N+1];
		for(int i = 1 ; i < N+1 ; i++) {
			drink[i] = Integer.parseInt(br.readLine());
		}
		
		dp[0] = 0;
		dp[1] = drink[1];
		
		if(N > 1) {
			dp[2] = drink[1] + drink[2];
		}
		
		System.out.println(grape(N));
}
	public static int grape(int d) {
			
	if(dp[d] == null)
dp[d] = Math.max(Math.max(grape(d - 2), grape(d - 3) + drink[d - 1]) + drink[d], grape(d - 1));
			
		return dp[d];
	}
}

포도주 시식 알고리즘을 푸는데 굉장히 헷갈렸습니다... 저에게는 이해하기 어려운 문제였습니다. 해당 문제에서 중요하다고 생각되는 점은 2가지입니다. 바로 문제의 이해와, 점화식 세우기입니다. STEP을 따라가 보며 보다 쉽게 이해하면서 문제를 풀이해 보도록 해요

---

알고리즘 흐름도

입력받기 -> dp 초기 설정해주기 -> 재귀 구현하기 (비교 3단계) -> 출력하기

 

비교 3단계는 마지막에 요약하여 설명했습니다.

---

STEP1 문제 이해하기

문제에 주어진 조건은 1가지입니다.

 

바로 연속으로 3잔을 마실 수 없다는 것입니다. 이 점에 가장 유의하며 문제를 풀이해야 합니다. 잘못하면 인덱스가 넘어가는 현상이 자주 일어나기 때문이죠.

 

그다음으로 고려해야 될 점은 바로 마실 수 있는 포도주의 양이 최대여야 한다는 점입니다.

 

만약 이전에 쉬운 계단 수 또는 계단 오르기 알고리즘을 풀어보시지 않았다면, 이해하기 어려운 문제라고 생각합니다. 해당 이해를 위해 계단 관련 알고리즘은 아래 링크를 참조해 주세요

[백준알고리즘-JAVA]2579번 풀이(계단 오르기) - 초보도 이해하는 풀이

 

[백준][JAVA알고리즘]10844번 풀이(쉬운 계단 수) - 초보도 이해하는 풀이

---

STEP2 dp배열 이해하기 및 초기값 설정

문제를 풀이하기 앞서서 dp배열을 왜 선언하고 사용하는지 알아야 합니다.

 

우선 dp는 dynamic plan의 약자로 자주 쓰이는 단어입니다. (물론 다른 단어 사용해도 무관합니다. 관습적으로 사용)

 

dp배열은 동적 계획법 문제에서 메모 이제이 션 기법을 사용하기 위해서 값이 있다면, 더 이상 재귀를 진행하지 않아도 됨을 뜻하게 되는 배열이면서, 저희가 답을 구하기 위한 최댓값이 담겨있는 배열입니다.

 

아주아주 쉽게 생각한다면 아래 표를 생각해 보셔야 합니다. (입력 예시를 이용)

 

인덱스	0	1	2	3	4	5
입력	6	10	13	9	8	1
dp	0	0	0	0	0	0

이런 식으로 선언을 해주는 것이 중요합니다.

 

이제 문제와 함께 진행해 보도록 하죠. 이해하기 어렵다면 막일로 이해하면 될 뿐!

 

인덱스가 0만 있다면 가장 많이 마실 수 있는 경우는 바로 6 이 되죠.

 

인덱스가 1까지 있다면 가장 많이 마실 수 있는 경우는 바로 6 + 10 = 16이 되죠.

 

인덱스가 2까지 있다면 가장 많이 마실 수 있는 경우는 6+10 또는 6+13 또는 10 + 13 중 큰 수인 23이 되겠죠.

 

인덱스	0	1	2	3	4	5
입력	6	10	13	9	8	1
dp	6	16	23	0	0	0

 

아직 이해가 안 되실 수도 있지만, 이 정도로 끄덕이며 그렇다면 첫 번째 dp는 무조건 자기 자신의 수가 되고 2번째의 경우 1, 2번째의 수를 더한 경우가 됩니다.

 

이에 따라 dp의 초기 값을 설정해 줍니다.

		dp[0] = 0;
		dp[1] = drink[1];
		
		if(N > 1) {
			dp[2] = drink[1] + drink[2];
		}

어? 근데 왜 dp [0]은 왜 0으로 해주나요? 하는 의문이 들 수 있습니다.

 

6 10 13 9 8 1

이런 식으로 입력이 들어와 있으면 dp를 구하기 위해서는 3번째 이전의 인덱스까지 값이 필요하기 때문입니다.

 

자 저희가 앞서서 1, 2번째의 dp의 초기 값을 설정해 줬던 건 기억하시죠?

 

그렇다면 3번째 dp는 어떻게 구해야 할까요?

 

자 아래와 같이 입력이 6개라면 3번째 값을 구하기 위해서는 

0 0 0 0 0 0 (6개)

v 0 v 0 0 0 (6+13)

0 v v 0 0 0 (10 + 13)

v v 0 0 0 0 (6 + 13)

(여기서 v는 경우의 수입니다.)

이런 식으로 구해야 합니다. 3잔을 연속으로 마실 수 없기 때문에 

 

자신보다 이전의 값과 자신보다 이이 이전의 dp(최댓값)을 더한 값과

자신 보다 이 이전의 최댓값을 비교해야 합니다.

쉽게 말해서 3번째 값을 구하기 위해서는 아무것도 안 마신 상태의 임의의 0 상태도 필요하기 때문이죠

0 0 0 0

v v 0 v

v 0 v v

이 둘 중의 무엇이 큰지 비교를 해야 하는 것이죠

 

그러면

0 v v 0 

이 경우가 크면 어떡하나요? 

당연히 이는 재귀를 구현하면서 고려해 줄 것입니다!

---

STEP 3 재귀 구현하기

 이전 STEP에서 이해가 덜 되셨다 해도 괜찮습니다. 구현해보면서 주입식으로 이해하셔도 좋습니다.

public static int grape(int d) {
			
	if(dp[d] == null)
	dp[d] = Math.max(Math.max(grape(d - 2), grape(d - 3) + drink[d - 1]) + drink[d], grape(d - 1));
			
	return dp[d];
	}

식이 굉장히 간단하죠?

 

첫 번째 if문은 당연히 메모이제이션을 위해 null을 가지고 있으면 재귀를 해주라는 의미

 

이제 하나씩 비교해 줍니다.

Math.max(grape(d - 2), grape(d - 3) + drink [d - 1])

 

grape(d-2) 의미 : 자신보다 2번째 이전 값의 최댓값 (dp를 의미)

grape(d-3) 의미 : 자신보다 3번째 이전 값의 최댓값 (dp를 의미)

drink [d-1] 의미 : 지산 보다 1번째 이전 값 (arr을 의미)

 

왜 다 drink로 안 하고 dp를 비교하나요?

다 drink로 계산한다면, 훨씬 이전의 값이 v 0 v 인지 v v 0인지 0 v v 인지 알지 못하기 때문이죠.

 

그러나 최댓값으로 비교해 준다면, 그 이전 값이 어떠한 방식으로 했든 3번 연속으로 마시는 조건을 만족할 수 있기 때문이죠.

 

결론적으로 이는 자신을 포한한 값입니다. 아까 step 2에서 마지막으로 고려해야 될 점으로 자기 자신을 포함하지 않는 값을 비교해서 큰 값을 dp에 넣어주며 끝!

---

설명이 너무 길어져서 이 말 저 말하여 이해하기가 쉽지 않았을 수도 있습니다. 간단히 요약해드리겠습니다.

 

해당 값의 최댓값을 알기 위해서 설계한 큰 틀

 - 자신을 포함하는가 vs 자신을 포함하지 않는가

 

자신을 포함하는가 에서 고려해야 될 상황

 - 자신과 3번째 이전의 최댓값 + 1번째 이전의 값 vs 자신과 2번째 이전의 최댓값

 

이렇게 3가지를 고려해 줍니다.

 

점화식으로 쉽게 이해하시는 방법도 있습니다. 다른 분의 링크를 참조해 보세요~

https://debuglog.tistory.com/80

---