백준 2156 - 포도주 시식 JAVA

문제, 입출력, 테스트케이스

제출현황(4트만에 맞췄다..!)

 

처음에 딱 보고??? 이거 계단 오르기 아닌가? 라고 생각 했지만 역시나 아니었다. 이유는 문제 풀이 과정에서!

 

<문제 접근/풀이 과정>
1. 포도주 잔 선택 시 무조건 다 마셔야 함
2. 3잔 연속으로 놓여 있는 잔을 마실 순 없음 -> 연속 +1, +1은 불가
3. 1 <= 포도주 잔의 갯수 <= 10,000 / 0 <= 포도주의 양 <= 1,000 
4. 처음에는 계단 오르기처럼 코드를 짰다가 광탈 당했다.
5. 잘 생각 해보니 포도주가 0만큼 들은 잔은 굳이 잔을 들 필요가 없다.  -> 계단 오르기는 무조건 계단을 올라가야 하기 때문에 n번 째의 포도주는 무조건 마신다는 조건과 같다. 하지만 해당 문제는 굳이 n번 째 잔을 마셔야 한다는 조건은 없다. (이 부분 고려 못해서 1, 2트 광탈!)
6.  n번 째 포도주 양이 0인 경우 n-1번 째까지에서의 최대로 마실 수 있는 양이 n번 째 잔에서 까지의 마실 수 있는 최대의 양이다. 
7. 또한 포도주가 1잔, 2잔 있을 때는 모두 마셔버리는 게 최대의 양이다. (이 부분 3트에서 고려 못해서 AIOOB 런타임에러 뜸)
9. 점화식
- n 번 째 포도주의 양이 0인 경우 : n-1번 째까지 마실 수 있는 최대의 포도주의 양
- n 번 째 포도주의 양이 1이 아닌 경우 : max(n-1번 째까지 마실 수 있는 최대 포도주의 양[계단 오르기와 다른 부분] or n번째잔 마심 + n-1번째 잔 마심 +  n-3번째 까지 마실 수 있는 최대의 양 or  n번째 잔 마심 + n-2번째까지 마실 수 있는 최대 포도주의 양(연속된 3잔을 마실 순 없기 때문에 계단오르기와 같은 점화식으로 푼다)

 

해당 DP문제는 바텀 업 방식으로 코드를 짰다.

package boj;

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

public class Boj_2156 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 1. 포도주 선택 시 다 마셔야 하고 원래 위치에 놓는다
		// 2. 연속으로 놓여있는 3잔 못마심 +1,+1 불가 ->
		// 최대로 마실 수 있는 포도주의 양은?
		// 1 <= 포도주 잔 갯수 n <= 10000, 0 <= 포도주 양 <=1000 -> 변수들 int 선언 가능
		// O
		// O O
		// X O O
		// O X O
		// O O X
		// O O X O
		// O X O O
		// O O X O O
		// O X O O X
		// X O O X O
		// O X O X O
		//
		// 점화식 도출 n번째까지의 최대로 마신양 = max(n-1번째까지 마신 최대의 양, n + (n-1번째 양 + n-3번째까지의 max), n
		// + (n-2번째까지의 max))
		// 포도주 양이 0 일 때는 들지 않기 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] wine = new int[n + 1]; // 0번째 패딩
		int dp[] = new int[n + 1];
		int answer = -1;

		for (int i = 1; i <= n; i++) {
			wine[i] = Integer.parseInt(br.readLine());
		}
		if (n < 3) { // n이 3보다 작으면
			for (int i = 1; i <=n; i++) {
				dp[i] = dp[i-1]+wine[i];
			}
			answer = dp[n];
		} else {
			dp[1] = wine[1];
			answer = Math.max(dp[1], answer);
			dp[2] = wine[2] + wine[1];
			answer = Math.max(dp[2], answer);

			for (int i = 3; i <= n; i++) {
				if (wine[i] == 0) { // i번째 포도주의 양이 0이면 이전까지의 max포도주가 최대
					dp[i] = dp[i - 1];
					answer = Math.max(dp[i], answer);
				} else { // i번째 포도주의 양이 0이 아니면
					dp[i] = Math.max(dp[i - 1], wine[i] + Math.max(wine[i - 1] + dp[i - 3], dp[i - 2]));
					answer = Math.max(dp[i], answer);
				}
			}
		}

		System.out.println(answer);
	}
}

DP도 꾸준히 풀다보니 점화식 찾는게 점점 재밌어진다. ^_^