문제
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
입력
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
출력
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
입출력 예
문제를 풀면서 수많은 틀렸습니다. 를 마주하면서 반례를 하나씩 찾다 보니 커스텀 테스트 케이스가 엄청나게 많아졌다...^^; 혹시라도 이 문제를 푸는데 반례를 일일히 찾기 힘드신 분은 여기서 찾아가시면 될 듯 ㅎㅎ
| 입력 | 출력 |
| 6 6 10 13 9 8 1 | 33 |
| 이 아래부터는 제가 임의로 추가한 테스트 케이스입니다. | |
| 6 1 2 3 4 5 6 (첫 잔을 안 마시는 경우) | 16 |
| 7 2 2 1 1 2 2 1 (마지막 잔을 안 마시는 경우) | 8 |
| 4 1 2 3 1 (첫 잔과 마지막 잔 둘 다 안 마시는 경우) | 5 |
| 10 1 1 1 1 1 1 1 1 1 1 (최대한 많은 잔을 마시는 경우) | 7 |
| 6 1000 1000 1 1 1000 1000 (두 잔 연속 안 마시는 경우) | 4000 |
| 10 977 200 517 851 23 662 880 815 26 214 (통상적인 경우) | 4254 |
| 7 1 10 1 10 1 10 1 | 32 |
| 7 100 1 100 1 100 1 100 | 400 |
| 7 1 1000 1000 1 1000 1000 1 | 4000 |
| 9 1 1000 1000 1 1 1 1000 1000 1 | 4001 |
서론
이 문제는 사실 과거 백준 알고리즘 문제풀이를 끄적끄적 하던 시절 손댔다가
풀지 못하고 방치해뒀던 문제였다.
최근에 다시 알고리즘 문제풀이 연습을 시작하면서 다시 풀게 됐다. 그래서 그동안 성장한(?) 만큼 과거의 내가 아니다 를 보여주며 복수를 하려 했으나..
그래도 결말은 해피 엔딩이긴 한데, 이번에는 문제를 풀면서 시행착오도 계속 겪어서 이 과정을 남겨두면 발상을 옮기는 방식을 기억해뒀다가 다른 문제에도 적용할 수 있을 것 같아서 글로 남기도록 하려고 한다. 짧게 줄이면 다음부터는 뻘짓하지 말자 라는 뜻이다.
풀이에 사용할 알고리즘 구상
누가 봐도 DP 문제니까, 일단 먼저 크기가 2인 배열을 원소로 받는 크기가 N인 이차원 DP 배열을 만들었다. 그리고, 직전의 포도주를 먹는 경우와 거른 경우 두 가지를 생각해서 직전의 포도주를 먹은 경우, 안 먹은 경우 각각의 최댓값을 저장해서 DP 배열에 넣는 방식으로 접근했다. 문제에서 주어진 예제(6 6 10 13 9 8 1)를 이 방식으로 풀면 정답이 바로 나온다.
그런데 제출하자마자 틀렸습니다. 를 만났다. 여러 가지 커스텀 테스트 케이스를 넣어 보니 포도주를 두 번 연속 먹지 않는 경우가 최적일 경우가 있었기 때문이었다. (ex. 입력이 6 1000 1000 1 1 1000 1000 인 경우)
그래서 DP 배열의 구성을 [직전의 포도주 잔을 고른 경우, 직전의 포도주 잔을 고르지 않은 경우, 두 번 연속 포도주 잔을 고르지 않은 경우]를 담는 이차원 배열로 바꿨다.
dp(n) = [dp(n-1)[1] + wine(n), dp(n-2)[0] + wine(n), Math.max(Math.max(...dp[n-3]), dp(n-1)[2]) + wine(n)]
그러나 이 방식은 전혀 통하지 않았고 오히려 여러 특수 케이스에 대해 결과가 들쭉날쭉해져서 DP 배열을 간소화해야겠다는 생각이 들었다.
그래서 DP 배열의 구성을 바꿨다. DP[i]에 정답을 저장할 때, 다음 세 가지 경우 중 가장 큰 값을 저장하면 된다고 생각했기 때문이다.
- 직전의 포도주를 마시고 이번 잔을 마신 경우
- 직전의 포도주를 마시지 않고 이번 잔을 마신 경우
- 직전 두 번 연속 포도주를 마시지 않고 이번 잔을 마신 경우
그리고 이 경우를 점화식으로 나타내면 다음과 같다. (DP는 정답을 담을 배열, WINE은 포도주 잔이 담긴 배열이라고 하자.)
- DP(N) = WINE(N) + WINE(N-1) + DP(N-3); (단, N < 3인 경우 DP(N-3)을 더하지 않는다.)
- DP(N) = WINE(N) + DP(N-2); (단, N < 2인 경우 DP(N-2)를 더하지 않는다.)
- DP(N) = WINE(N) + DP(N-3);
이렇게 나올 수 있는 세 가지 경우 중 가장 큰 값을 DP에 저장하면 되겠지? 하고 풀었다. 코드는 다음과 같다.
// switch문을 쓴 이유는, 코드 설계 과정에서 i가 2보다 작을 때 java.lang.ArrayIndexOutOfBoundsException이 발생할까봐..
switch (i) {
case 0:
dp[i] = wine[i];
break;
case 1:
dp[i] = wine[i] + dp[i-1];
break;
case 2:
dp[i] = Math.max(wine[i-1] + wine[i], dp[i-1]);
break;
default:
// 직전의 포도주 잔을 고른 경우,
// 3번 전의 포도주를 고른 경우의 최댓값과 직전, 현재 포도주 잔의 합과 같다.
int first = wine[i] + wine[i-1] + dp[i-3];
int second = wine[i] + dp[i-2];
int third = wine[i] + dp[i-3];
dp[i] = Math.max(Math.max(first, second), third);
}결론부터 말하자면 또 틀렸다. 왜 또 틀렸을까 해서 또 마구잡이로 커스텀 테스트 케이스를 넣어보기 시작했다. 그리고 찾아낸 정답은, 마지막 잔을 마시지 않은 경우가 더 많이 먹는 경우일 수도 있다는 것을 알아냈다.
글로 쓰니까 한줄짜리고, 정말 바보같지만 사실 이걸 생각해내는데 거의 30분 넘게 쓴 것 같다. 그리고 지금 이렇게 글로 회고하다 보니 알게 된 사실인데, 위에서 DP[i]에 들어갈 경우를 나눌 때 나도 모르게 모든 경우를 이번 잔을 마신 경우에 한정해서 생각했다는 사실을 알게 됐다. 당시에는 DP[i]니까 당연히 WINE[i]를 마시는 과정이 필요하다고 생각해서 범한 치명적인 실수였다. 어이없게도 이번 잔을 마시지 않는 경우는 DP[i]에 적용을 안 했던 것이다. 이렇게 되면 DP[i]에 최대로 마시는 경우가 저장되지 않아서 결국 정답이 출력되지 않는다.
따라서, DP[i]를 구한 뒤, 이를 한 번 더 DP[i-1]와 비교하는 과정이 필요하다.
그리고 지금 이렇게 글로 정리하다 보니 하나 더 보였는데, 모든 상황에 대해서 third가 first보다 작다는 사실을 발견했다.. DP 배열의 구성을 바꾸기 전에는 DP가 이차원 배열이어서 모든 케이스를 저장해두는 역할을 했는데, 이 때의 흔적이 남아 불필요한 방식으로 코드를 짠 것 같다. DP 배열이 항상 최댓값을 저장하도록 바꾼 현재로서는 third 변수가 필요 없어졌다.
가독성이 낮은 switch문을 if문으로 고치고, third를 삭제하여 리팩토링을 진행한 결과는 다음과 같다.
제출 코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력 받기
int n = sc.nextInt();
// wine : 포도주 잔에 들어있는 포도주의 양
int[] wine = new int[n];
// dp[i] : i번째 잔까지 최대로 마실 수 있는 포도주의 양
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
wine[i] = sc.nextInt();
if (i == 0) {
dp[i] = wine[i];
continue;
}
// i번째 포도주 잔을 고른 경우
int first = 0, second = 0;
// // 두 번 연속하여 포도주 잔을 고르지 않은 경우는 항상 first보다 작아서 고려하지 않는다.
// if (i >= 3) third = dp[i-3] + wine[i];
// // 직전의 포도주 잔을 고르지 않은 경우
if (i >= 2) second = wine[i] + dp[i-2];
// // 직전의 포도주 잔을 고른 경우
if (i >= 1) first = wine[i] + wine[i-1];
if (i >= 3) first += dp[i-3]; // i < 3인 경우 dp[i-3]을 호출하면 java.lang.ArrayIndexOutOfBoundsException 발생
dp[i] = Math.max(first, second);
// i번째 포도주 잔을 고르지 않은 경우
// 예시: 1000 1000 1에서는 3번째 잔을 먹지 않는 게 더 이득이다.
// 이 때는, dp[i-1]이 dp[i]보다 클 것이다.
dp[i] = Math.max(dp[i-1], dp[i]);
}
int answer = 0;
for (int dpValue : dp) answer = Math.max(answer, dpValue);
System.out.println(answer);
sc.close();
}
}회고
DP 문제에 접근할 때는 대부분의 경우 DP에 최댓값 또는 최솟값만을 저장하여 간단한 상태로 두는 게 좋다는 사실을 다시금 깨닫게 됐다. 초반에 DP를 이차원 배열로 만들다 보니 시간을 너무 허비했고, 결국 최종 제출 직전까지 third라는 불필요한 변수를 남기는 악영향을 끼쳤다.
그래도 커스텀 테스트 케이스를 너무 많이 만들다보니 대부분의 경우에서 정답이 맞는 것 같아서 문제를 풀면서 왜 틀렸는지 이해가 가질 않아서 많이 지쳤는데 끝까지 포기하지 않고 풀어내서 스스로가 기특하긴 했다. 사실 지금 글을 쓴 것도 풀이 과정을 단순화한거지, 별도의 클래스를 만들어서 DP의 세 경우의 최댓값을 비교하는 메소드도 만들고, 두 번 연속하여 포도주 잔을 고르지 않은 경우를 어떻게 표현해야 할 지 생각하다가 세 번 전의 DP 중 최댓값과 직전의 DP의 3번째 값을 비교하여 더 큰 값을 집어넣는 등 별의별 시도를 다 해본것 같다.. 그래도 문제를 푸는 데 어느 정도 감을 잡고 리팩토링을 거치고 나니 코드가 깔끔하게 보여서 다행인 것 같다 휴
DP는 정말 해도해도 끝이 없는 것 같다^^ 나도 수학 전공 했으면 DP 더 잘 풀었으려나 하;;
'Algorithm > 동적 계획법' 카테고리의 다른 글
| [백준/2193번/C++] 이친수 (0) | 2020.08.03 |
|---|
