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

문제내용

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

2156번: 포도주 시식

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

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

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

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

입력

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

출력

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

 

---

문제 접근 방법

문제는 백준의 계단오르기(2579) 문제와 매우 비슷한 문제이다.

처음에는 계단오르기 문제와 같은 로직으로 풀었는데 조건을 추가안해서 틀렸다. 틀린이유는 두개이다.

1. 계단오르기의 경우 마지막 계단을 밟아야만하는데 여기선 마지막잔 안마셔도 그전이 최대값이라면 굳이 마지막잔 안마셔도됨.
2. 두 문제다 연속되는 3개의 값을 사용할 수 없다. 하지만 계단오르기는 입력값을 사용하지 않는 경우엔 한칸만 뛰어 넘을 수 있으나 포도주 시식의 경우 한칸이든 두칸이든 세칸이든 포도주 값을 사용하지 않고 뛰어넘을 수 있음.

위의 경우를 고래서해서 점화식을 풀어내면된다. 이때 입력받는 포도주의 값은 podo배열에 저장했고, dp배열의 경우 dp[포도잔개수] = 최댓값(누적값) 으로 정의했다.

 

먼저 계단오르기의 문제를 풀어봤다면 

dp[n] = dp[n-2] + podo[n] (한칸건너 뛰고 시식한 경우)

dp[n] = dp[n-3] + podo[n-1]+podo[n] (바로 전 시식한 경우)

dp[n] = Math.max(재귀(n-2) , 재귀(n-3) + podo[n-1]) + podo[n];

식을 이해할수 있을것이다.

 

그럼 위의 점화식에 조건을 추가하기만하면 된다.

1. 위에서 첫번째로 말한 1번 조건 추가를 위해선 마지막 값이 최대인지 전값이 최대 인지 비교해주기만 하면된다.

  -> dp[n] = Math.max(Math.max(재귀(n-2) , 재귀(n-3) + podo[n-1]) + podo[n]), 재귀(n-1));

2. 두번째 조건은 포도주를 마시지않고 건너뛰는 경우이다. 이때 포도주를 마시지 않고 두칸이상 건너뛰어야 하는 이유는 입력 받은 포도주 값이 0일때 뿐이다.(0인 포도주잔을 든다면 최댓값은 늘어나지않고 기회비용만 날아감.)

  -> if(podo[n] == 0) { dp[n] = 재귀(n-1); }

 

점화식에 위의 조건을 추가해서 풀어내며 답이된다.

풀이를 보자.

 

---

풀이

TopDown

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

public class BOJ_2156_1 {
	static int[] dp;
	static int[] podo;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		dp = new int[n+1]; //0번인덱스 사용안함
		podo = new int[n+1]; //마찬가지
		
		for(int i=1; i<=n; i++) {//입력값 및 dp 배열 초기화
			podo[i] = Integer.parseInt(br.readLine());
			dp[i] = -1;
		}
		dp[1]=podo[1]; //포도주가 1잔일때는 무조건 podo[1]. 초기화
		
		//아래 재귀에서 n=2가 드가면 인덱스에러뜸.
		//그거 안뜨게 dp[2] 초기화 시켜줘야됨.
		if(n>=2) {
			dp[2] = podo[1]+podo[2];
		}
		
		System.out.println(maxPodo(n));
	}
	
	public static int maxPodo(int n) {
		if(dp[n]==-1) {//계산 안된경우 아래처럼 계산
			if(podo[n]==0) {//만약 podo[n]이 0이면 마실필요 없음. 걍 다음으로 넘어감.
				dp[n]=maxPodo(n-1);
			}else {//그게 아니면 비교 후 계산값 할당
				dp[n] = Math.max(Math.max(maxPodo(n-2), maxPodo(n-3)+podo[n-1]) + podo[n], maxPodo(n-1));
			}
		}
		return dp[n];
	}

}

 

BottomUp

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

public class BOJ_2156_2 {
	static int[] dp;
	static int[] podo;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		dp = new int[n+1]; //0번인덱스 사용안함
		podo = new int[n+1]; //마찬가지
		
		for(int i=1; i<=n; i++) {//입력값 및 dp 배열 초기화
			podo[i] = Integer.parseInt(br.readLine());
			dp[i] = -1;
		}
		dp[1]=podo[1]; //포도주가 1잔일때는 무조건 podo[1]. 초기화
		
		//아래 for문에서 n=3부터 시작함. n<=2부터 시작하면 인덱스에러 뜸.
		//그거 안뜨게 dp[2] 초기화 시켜줘야됨.
		if(n>=2) {
			dp[2] = podo[1]+podo[2];
		}
		
		for(int i=3; i<=n; i++) {
			if(podo[i]==0) {
				dp[i] = dp[i-1];
			}else {
				dp[i] = Math.max(Math.max(dp[i-2], dp[i-3]+podo[i-1])+podo[i], dp[i-1]);
			}
		}
		
		System.out.println(dp[n]);
	}

}

 

---

마치며

topDown이나 bottomUp이나 점화식만 안다면 쉽게 풀어낼 수 있다.

그리고 dp공부를 할때 점화식을 찾고 topDown부터 푸는게 좋다고들 한다.. 어차피 재귀로 풀수 있으면 반복문으로도 풀수 있는거라서 그런듯하다. 여튼 이번문제는 조건을 좀더 생각해봤다면 더빨리 풀수 있지 않았을까 생각한다.