[BaekJoon] 2156 포도주 시식

1.  문제 링크

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

2.  문제

요약

• 여러 개의 포도주 잔이 일렬로 놓여있고 포도주를 시식하려고 하는데 아래 두 규칙을 지키며 시식하려고 합니다.
  • 포도주 잔을 선택하면 해당 잔의 포도주를 모두 마시고 마신 후에는 원위치에 다시 놓습니다.
  • 연속으로 놓여 있는 3잔을 마실 수 없습니다.
• n개의 포도주 잔이 순서대로 테이블에 놓여있고, 각 포도주 잔에 들어있는 포도주 양이 주어졌을 때, 마실 수 있는 가장 많은 양의 포도주 양을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 포도주 잔의 개수 n이 주어지고 두 번째 줄부터 n개의 줄에는 0보다 크거나 같고 1,000보다 작거나 같은 포도주의 양들이 주어집니다.
• 출력: 첫 번째 줄에 최대로 마실 수 있는 포도주 양을 출력합니다.

3.  소스코드

Top-Down 방식

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

public class Main {
	static int[] size;
	static Integer[] dp;
	public int findMaxSize(int num) {
		if(dp[num] == null) {
			dp[num] = Math.max(Math.max(findMaxSize(num - 2), findMaxSize(num - 3) + size[num - 1]) + size[num], findMaxSize(num - 1));
		}
		return dp[num];
	}
	
	public int getMaxSize() {
		dp = new Integer[size.length];
		dp[0] = size[0];
		dp[1] = size[1];
		if(size.length - 1 >= 2) {
			dp[2] = size[1] + size[2];
		}
		return findMaxSize(dp.length - 1);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		size = new int[num + 1];
		for(int i = 1; i <= num; i++) {
			size[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxSize() + "\n");
		bw.flush();
		bw.close();
	}
}

Bottom-Up 방식

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

public class Main {
	public int getMaxSize(int[] size) {
		int[] dp = new int[size.length];
		dp[1] = size[1];
		if(size.length - 1 >= 2) {
			dp[2] = size[1] + size[2];
		}
		for(int i = 3; i < dp.length; i++) {
			dp[i] = Math.max(Math.max(dp[i - 2], dp[i - 3] + size[i - 1]) + size[i], dp[i - 1]);
		}
		return dp[dp.length - 1];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] size = new int[num + 1];
		for(int i = 1; i <= num; i++) {
			size[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxSize(size) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 해결할 수 있습니다.
• DP는 재귀함수를 사용하는 Top-Down 방식과 반복문을 사용하는 Bottom-Up 방식이 존재하고 두 방식으로 풀이해보았습니다.

Top-Down 방식

• 배열 dp에 첫 번째 잔일 때부터 시작하여 해당 개수에서의 최대로 마실 수 있는 포도주 양을 구해나가는데, 이전 잔에서의 최대로 마실 수 있는 포도주 양을 이용하여 구해나갑니다.
• 첫 번째 잔일 때는 첫 번째 잔의 포도주 양, 두 번째 잔일 때는 첫 번째 잔과 두 번째 잔 포도주 양의 합이 최대로 마실 수 있는 포도주 양이기 때문에 해당 값으로 초기화해줍니다.
• 문제의 조건에서 3잔을 연속으로 마실 수 없다고 하였기 때문에 (두 잔 전의 최대로 마실 수 있는 양)과 (세 잔 전의 최대로 마실 수 있는 양 + 바로 이전 잔에 들어있는 포도주 양) 중 더 많은 양과 현재 잔에 들어있는 포도주 양의 합을 구하여 현재 잔에서의 최대로 마실 수 있는 양을 구합니다.

public int findMaxSize(int num) {
	if(dp[num] == null) {
		dp[num] = Math.max(findMaxSize(num - 2), findMaxSize(num - 3) + size[num - 1]) + size[num];
	}
	return dp[num];
}

• 하지만 마지막 dp의 값이 항상 최댓값이 아니기 때문에 위에서 구한 값을 바로 이전 잔에서의 최대로 마실 수 있는 양과 비교하여 더 많은 양으로 현재 잔에서의 최대로 마실 수 있는 양을 갱신합니다.

public int findMaxSize(int num) {
	if(dp[num] == null) {
		dp[num] = Math.max(Math.max(findMaxSize(num - 2), findMaxSize(num - 3) + size[num - 1]) + size[num], findMaxSize(num - 1));
	}
	return dp[num];
}

• 위 점화식을 바탕으로 최대로 마실 수 있는 양을 구합니다.

1. 주어진 포도주 잔들에서의 최대로 마실 수 있는 양을 나타내는 dp 배열을 생성하고 값을 초기화시킵니다.

   • Integer 배열로 생성하여 초기화를 해주지 않으면 null이 되기 때문에 0번 index의 값을 0으로 초기화시킵니다.
   • 첫 번째 잔에서의 최대로 마실 수 있는 포도주 양은 첫 번째 잔의 포도주 양이기 때문에 해당 값으로 초기화시킵니다.
   • 만약 주어진 포도주 잔의 개수가 1개를 넘는다면 두 번째 잔에서의 최대로 마실 수 있는 포도주 양은 (첫 번째 잔의 포도주 양 + 두 번째 잔의 포도주 양)이기 때문에 해당 값으로 초기화시킵니다.

2. 재귀함수를 통하여 최대로 마실 수 있는 포도주 양을 구합니다.

   • 초기화시킨 두 값과 위에서 구한 점화식을 이용하여 마지막 잔에 도달할 때까지 각 잔에서의 최대로 마실 수 있는 포도주 양을 dp 배열에 저장하고 이를 이용하여 최대로 마실 수 있는 포도주 양을 구합니다.

3. 2번의 재귀함수를 통해 구한 최대로 마실 수 있는 포도주 양을 출력합니다.

Bottom-Up 방식

• Top-down 방식에서 구한 점화식을 바탕으로 재귀함수를 반복문으로 변경합니다.
• 문제의 조건에서 3잔을 연속으로 마실 수 없다고 하였기 때문에 (두 잔 전의 최대로 마실 수 있는 양)과 (세 잔 전의 최대로 마실 수 있는 양 + 바로 이전 잔에 들어있는 포도주 양) 중 더 많은 양과 현재 잔에 들어있는 포도주 양의 합을 구하여 현재 잔에서의 최대로 마실 수 있는 양을 구합니다.

for(int i = 3; i < dp.length; i++) {
	dp[i] = Math.max(dp[i - 2], dp[i - 3] + size[i - 1]) + size[i];
}

• 하지만 마지막 dp의 값이 항상 최댓값이 아니기 때문에 위에서 구한 값을 바로 이전 잔에서의 최대로 마실 수 있는 양과 비교하여 더 많은 양으로 현재 잔에서의 최대로 마실 수 있는 양을 갱신합니다.

for(int i = 3; i < dp.length; i++) {
	dp[i] = Math.max(Math.max(dp[i - 2], dp[i - 3] + size[i - 1]) + size[i], dp[i - 1]);
}