[Brute Force] 5638번 - 수문

🔗 문제 링크

백준 5638번 - 수문

📝 풀이

수문의 유량과 비용이 주어지면 일정시간 안에 목표 양을 비워야 한다.
combination 함수에 인자로 수문의 유량 * 주어진 시간을 더한 sum값을 넘겨서 sum이 목표 양보다 크면 비용을 비교하도록 코드를 짰다.
재귀함수를 사용해서 결국 min 변수에는 최소 비용이 저장될 것이다.

최소비용만 반환하면 되는 문제인데 예시를 보고 수문마다 구체적인 시간까지 계산해야 하는 것으로 착각하는 탓에 갈피를 잡지 못했다.

문제에서 요구하는 것이 무엇인지 앞으로 정확하게 읽고 파악해야겠다.

cnt: 현재까지 선택한 게이트의 수
start: 현재 고려 중인 게이트의 인덱스.
sum: 현재까지 선택한 게이트들의 전체 유량 합
visited: 선택된 게이트를 구분하기 위한 boolean 배열

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 수문_5638 {
    static class Gate {
        int flow;
        int cost;

        public Gate(int flow, int cost) {
            this.flow = flow;
            this.cost = cost;
        }
    }

    static int n, v, time, min;
    static Gate[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new Gate[n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int f = Integer.parseInt(st.nextToken()); //유량
            int c = Integer.parseInt(st.nextToken()); //비용
            arr[i] = new Gate(f, c);
        }

        int m = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < m + 1; i++) {
            st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken()); //비워내야 하는 물의 양
            time = Integer.parseInt(st.nextToken()); //제한 시간
            min = Integer.MAX_VALUE;
            combination(0, 0, 0, new boolean[n]);

            sb.append("Case " + i + ": ").append(min == Integer.MAX_VALUE ? "IMPOSSIBLE" : min).append("\n");
        }

        System.out.println(sb);
    }

    private static void combination(int cnt, int start, int sum, boolean[] visited) {
        if (sum >= v) {
            int tmp = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) { //선택했던 게이트라면 비용 추가
                    tmp += arr[i].cost;
                }
            }

            min = Math.min(min, tmp);
            return;
        }

        if (cnt == n) {
            return;
        }

        for (int i = start; i < n; i++) {
            if (!visited[i]) {
            	visited[i] = true;
                combination(cnt + 1, i + 1, sum + arr[i].flow * time, visited);
                visited[i] = false; //다음 게이트를 선택하여 최소비용 계산을 위해 이미 계산된 게이트는 false 처리
            }
        }
    }

}