문제
https://www.acmicpc.net/problem/2156
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
입력
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
출력
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
풀이
기본적인 접근 방법은 계단 오르기 문제와 유사하다. 그러나 푸는 동안 너무 많은 반례를 만났다. 이 문제에서 가장 주의해야 할 점은 현재 위치의 와인을 마시지 않아도 된다는 것이다. 동적 계획법을 사용할 예정이라, 현재 위치의 와인을 마시지 않을 때 더 많이 마실 수 있는 경우에는 이전 dp값을 저장해주면 된다.
여러 가지 예제를 살펴보며 문제를 풀어보자.
분홍색 표는 포도주 잔의 개수와 포도주의 양을 순서대로 나타낸 표이다.
초록색 표는 dp 배열에 저장되는 각 index의 값이다.
-
dp[0]의 경우 cost[0]과 같다. dp[1]의 경우 cost[0]과 cost[1]을 더한 값과 같다.
-
dp[2]의 경우, 처음에는 계단 오르기 문제를 생각해서 cost[0]과 cost[1] 중 최댓값을 택하고 cost[2]를 더해주면 된다고 생각했다. 그러나 계단 오르기 문제의 경우 마지막 계단은 반드시 밟아야 하는 조건이 있었지만 이 문제의 경우 현재 위치의 와인을 마시지 않아도 상관없다. 현재 위치의 와인을 마시면 앞의 두 개 와인을 모두 마시지는 못하기 때문에 손해이다. 따라서 dp[2]의 경우 현재 위치의 와인을 마시지 않고 이전 dp인 dp[1]을 저장해주어야 한다.
-
dp[3]의 경우도 현재 위치의 포도주를 선택하면 손해이기 때문에 dp[2] 값을 저장해준다.
-
dp[4]의 경우 dp[2]에 현재 위치의 포도주양인 cost[4]를 더해주면 최댓값이다.
dp[5]의 경우도 마찬가지로 dp[3]에 현재 위치의 포도주양인 cost[5]를 더해주면 최댓값이다.
따라서 답은 400이 나와야 한다.
다음 예제는 다음과 같다.
- dp[0] : cost[0]
- dp[1] : cost[0] + cost[1]
- dp[2] : cost[1] + cost[2]
- dp[3] : 현재 위치의 포도주를 선택하는 경우보다 선택하지 않고, 이전 dp를 가져가는 것이 더 이득이다.
- dp[4] : dp[2] + cost[4]
- dp[5] : dp[2] + cost[4] + cost[5]
이를 바탕으로 간단하게 식을 세워보면 다음과 같다. (Bottom-Up)
dp[0] = cost[0];
dp[1] = cost[0] + cost[1];
dp[2] = Math.max(dp[1], Math.max(cost[0], cost[1]) + cost[2]);
for(int i = 3; i < N; i++) {
dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + cost[i-1], dp[i-2]) + cost[i]);
}Bottom-Up (반복문 사용)
전체 코드
import java.io.*;
import java.util.*;
class Main {
public static int[] dp;
public static int[] cost;
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 N = Integer.parseInt(br.readLine());
cost = new int[N];
for (int i = 0; i < N; i++) {
cost[i] = Integer.parseInt(br.readLine());
}
bw.write(String.valueOf(dfs(N)) + "\n");
bw.flush();
bw.close();
}
public static int dfs(int N) {
dp = new int[N];
dp[0] = cost[0];
if (N > 1) dp[1] = cost[0] + cost[1];
if (N > 2) dp[2] = Math.max(dp[1], Math.max(cost[0], cost[1]) + cost[2]);
for (int i = 3; i < N; i++) {
dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 3] + cost[i - 1], dp[i - 2]) + cost[i]);
}
return dp[N - 1];
}
}N의 값이 1, 2일 때를 따로 체크해주었다.
Top-Down (재귀 사용)
전체 코드
import java.io.*;
import java.util.Arrays;
public class Main {
public static int[] dp;
public static int[] arr;
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 n = Integer.parseInt(br.readLine());
dp = new int[n + 1];
arr = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(br.readLine());
dp[i] = -1;
}
dp[1] = arr[1];
if (n > 1) {
dp[2] = arr[1] + arr[2];
}
if (n > 2) {
dp[3] = Math.max(arr[1] + arr[2], Math.max(arr[2] + arr[3], arr[1] + arr[3]));
}
System.out.println(dfs(n));
}
public static int dfs(int n) {
if (dp[n] == -1) {
dp[n] = Math.max(dfs(n - 3) + arr[n - 1] + arr[n], Math.max(dfs(n - 2) + arr[n], dfs(n - 1)));
}
return dp[n];
}
}n==1, n==2, n==3인 경우를 먼저 dp에 초깃값으로 저장한 다음, Top-Down 방식으로 재귀를 사용하여 풀이하였다.
실수한 것들
현재 위치의 포도주를 마시지 않는 것이 이득일 수도 있다. 예를 들어 1000, 1000, 1, 1일 경우를 가정하자. 초기값은 dp[0] = 1000, dp[1] = 2000로 설정한다. dp[2]를 구할 때 해당 위치의 포도주를 마시지 않고 dp[1]의 선택을 따라가는 것이 더 이득이다. 현재 위치의 포도주를 마시게 되면 1001, 마시지 않는다면 2000만큼 마실 수 있기 때문이다. 따라서 dp[i]를 구할 때는 dp[i-1]과 비교를 해주어야 한다.
86%에서 자꾸 틀리길래 한참을 쳐다보다가 발견한 사실은...
public static int dfs(int N) {
dp = new int[N];
if (N == 1) return cost[0];
if (N == 2) return cost[0] + cost[1];
if (N == 3) return Math.max(dp[1], Math.max(cost[0], cost[1]) + cost[2]);
dp[0] = cost[0];
dp[1] = cost[0] + cost[1];
dp[2] = Math.max(dp[1], Math.max(cost[0], cost[1]) + cost[2]);
for (int i = 3; i < N; i++) {
dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 3] + cost[i - 1], dp[i - 2]) + cost[i]);
}
return dp[N-1];
}이 코드에서 문제점은 N==3일 경우 계산되지 않은 dp[1]값을 사용한다는 점이다. 동적계획법 문제를 풀 때 N의 범위를 체크하는 과정에서 실수가 잦다.
N==3, 포도주의 양이 다음과 같이 주어졌을 때 답이 101이 나온다. dp[1]이 아직 0이기 때문에 cost[0] + cost[2]의 값인 101이 더 큰 값이다.
코드를 다음과 같이 고쳐야 한다.
public static int dfs(int N) {
dp = new int[N];
if (N == 1) return cost[0];
if (N == 2) return cost[0] + cost[1];
if (N == 3) return Math.max(cost[0] + cost[1], Math.max(cost[0], cost[1]) + cost[2]);
dp[0] = cost[0];
dp[1] = cost[0] + cost[1];
dp[2] = Math.max(dp[1], Math.max(cost[0], cost[1]) + cost[2]);
for (int i = 3; i < N; i++) {
dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 3] + cost[i - 1], dp[i - 2]) + cost[i]);
}
return dp[N-1];
}또는
public static int dfs(int N) {
dp = new int[N];
dp[0] = cost[0];
if (N > 1) dp[1] = cost[0] + cost[1];
if (N > 2) dp[2] = Math.max(dp[1], Math.max(cost[0], cost[1]) + cost[2]);
for (int i = 3; i < N; i++) {
dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 3] + cost[i - 1], dp[i - 2]) + cost[i]);
}
return dp[N - 1];
}
이렇게 바꾸는게 조금 더 깔끔한 것 같다.
