BOJ | Silver 1/5638/수문

12시간 이상 문제를 고민하지 마세요(제발...)

 필자는 dp 방식으로 풀기 위해 메모이제이션에 사용할 배열을 잘못 생성하여 본 문제에 대해 12시간 이상을 고민했다. 독자는 그러지 마시길 바라며 글을 시작한다. 

1. 문제 이해

_

댐은 n개의 수문을 가지고 있다. 각각의 수문은 자체 용량과 물길을 가지고 있고, 하류에 영향을 줄 수 있다. 
수문이 열렸을 때, 영향을 받는 지역은 홍수의 위험이 있다. 수문에 의한 예상 피해액은 지역의 인구의 수와 면적으로 계산할 수 있다.

수문 Gi의 유량이 Fi m3/hour 이고, 피해 비용이 Ci라고 하자. 댐에는 물이 Vm3 만큼 저장되어 있고, 이 물을 T시간 이내에 모두 비워내야 하는 상황이다. 이때, 수문을 어떻게 열어야 피해 비용이 최소가 되는지를 구하는 프로그램을 작성하시오.

예를 들어, 댐에 수문이 4개가 있고, 각 수문의 유량과 피해 비용이 아래와 같다고 하자.

물 5백만 m3을 7시간 안에 비워내야 하는 경우에, G1을 7시간동안 열어 놓으면 되고, 비용은 120,000이 된다. 
물 5백만 m3을 30시간 안에 비워내야 하는 경우에는 G2를 29시간, G3를 28시간 동안 열어 놓으면 된다. 이때의 비용은 110,000이 된다. 모든 수문은 항상 독립적으로 동작하며, 수문은 항상 1시간 단위만큼 열 수 있다.

_

위 문제를 분석하면 다음과 같다. 주어진 댐에 저장된 물의 양과 주어진 시간 안에, 각 수문을 통해 나가는 물의 양을 체크한다. 이때, 선택된 수문에 따른 비용이 결정이 된다. 위 예시에 따르면 G1만 선택되면 120,000이고, G2와 G3가 선택되면 110,000이다.그래서 그 피해 비용을 최소로 만드는 경우를 출력시키면 된다.

여기서의 포인트는 어떤 문을 선택하느냐다. 피해 비용은 문을 선택하면서 결정되기 때문에, 문을 통해 나가는 물의 양을 구체적으로 구할 필요가 없었다. (이 부분을 투포인터로 해결하려고 했던 나 반성)

 

2. 로직

2-1) 로직 플로우

수문 정보인 유량과 피해 비용을 입력받고, 테스트 케이스인 댐에 저장된 물의 양과 비워내야 하는 시간을 입력받는다. 유량 정보는 비워내야 하는 시간을 곱해서 각각의 값을 다른 배열에 담아서 사용할 것이다. 그리고 이 배열의 부분집합을 구하는 방식으로 배열의 각 인덱스에 할당된 값을 완전탐색 하면서, 비워야 하는 물의 총량을 만족하는 동시에 피해 비용이 최소가 되는 경우를 찾아서 출력시킨다.

2-2) 로직 상세

1) 수문을 통해 나가는 유량 정보인 G와 각 수문을 통해 선택되는 비용인 C를 배열을 생성하여 이를 할당

2) 댐에 저장된 물의 양인 V와 비워야 하는 시간인 T를 배열을 생성하여 이를 할당

3) 각 수문을 통해 내보내는 유량을 비워야 하는 시간인 T와 곱해서 이를 temp 배열에 할당 

4) dp 배열을 생성한다. 그리고 비트마스킹으로 부분집합을 구하면서 temp 배열의 값을 dp 배열에 누적시키며 할당.

5) 누적시킨 값이 댐에 저장된 물의 양보다 크거나 같은 경우, 출력시킬 변수에 그 값을 할당

6) 매 테스트 케이스마다 4, 5를 반복하여 StringBuffer 객체에 그 값들을 추가 

7) temp 배열의 값을 모두 더한 값이 수문을 통해 내보낼 수 있는 유량의 총량인데, 그 값을 초과하는 경우에는 StringBuffer 객체에 IMPOSSIBLE을 할당

8) StringBuffer 객체를 String 객체로 생성 후 출력.
 

3. 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        List<long[]> expense = new ArrayList<>();
        List<long[]> possibility = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            expense.add(new long[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            possibility.add(new long[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }

        StringBuffer sb = new StringBuffer();
        long maxExpense = 0l;
        for (int i = 0; i < expense.size(); i++) {
            maxExpense += expense.get(i)[1];
        }


        for (int i = 0; i < possibility.size(); i++) {
            long storageDam = possibility.get(i)[0];
            int value = (int) possibility.get(i)[1];

            long minExpense = maxExpense + 1;
            long[] temp = new long[expense.size()];
            int[] dp = new int[1<<n];
            long[] totalExpense = new long[1<<n];

            for (int j = 0; j < expense.size(); j++) {
                temp[j] = value * expense.get(j)[0];
            }

            for (int j = 1; j < (1<<n); j++) {
                for (int k = 0; k < n; k++) {
                    if ((j & 1 << k) != 0) {
                        dp[j] += (int) temp[k];
                        totalExpense[j] += (int)expense.get(k)[1];
                    }
                }
                if(dp[j] >= storageDam) {
                    minExpense = Math.min(minExpense, totalExpense[j]);
                }
            }

            if (minExpense > maxExpense)
                sb.append("Case ").append(String.valueOf(i + 1)).append(": IMPOSSIBLE").append("\n");
            else sb.append("Case ").append(String.valueOf(i + 1)).append(": ").append(minExpense).append("\n");
        }

        System.out.print(new String(sb));
        sb.setLength(0);
    }
}

 

4. 마치며

본 문제를 풀기 위해 자료를 찾아봤었는데, JAVA로 작성된 참고자료가 없다는 것을 알게 되었다. 그것과 더불어서 12시간 이상을 문제 푸는데 사용하다보니, 누군가는 나처럼 오랜 시간을 소비하지 않았으면 했다. 그래서 이 포스팅을 작성하게 되었다.

본 문제 알고리즘 분류에 이분탐색이 적혀있었는데, 다 풀고 난 뒤, 글의 시작에 첨부된 사진처럼 작성했는데 알고리즘 분류에 이분 탐색과 비트마스킹이 지워지게 되었다. 이분탐색과 비트마스킹으로 접근한다는 것 자체가 문제에서 물을 방류하는 시간을 모든 경우로 나눠서 탐색할 필요가 없다는 의미기 때문에, 결정적인 힌트여서 그런걸까 싶다.

본 문제의 풀이는 비트마스킹으로 작성된 점, 필자가 접근했던 시간을 세분화 해서 모든 경우를 dp에 담아서 이분탐색 하는 방법은 잘못된 방법이다. 독자는 그 실수를 하지 않기를 바란다. 직접 문제를 풀어봄으로써 위 내용을 확인해보면 좋을 것 같다. 끝까지 읽어주신 독자에게 무한한 감사를 드린다 :)
https://www.acmicpc.net/problem/5638

5638번: 수문