[백준] 5638: 수문 - JAVA

14 Sep 2023 in Algorithm on 브루트포스 알고리즘

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

풀이

수문의 유량과 비용이 주어지고 일정 시간 안에 일정 양을 비워야 하는 문제이다.

물 500을 30시간 안에 비우려면

유량 5, 비용 60인 수문을 29시간,

유량 13, 비용 50인 수문을 28시간 열어놓으면 되고, 비용은 110이 된다.

수문의 최대 개수가 20으로 주어져있어서 조합으로 만들어 체크하기로 했다.

combination 메서드에 인자로 (수문의 유량 * 주어진 시간)을 더한값을 넘겨서

그 값이 목표 양보다 크면 비용을 비교해주었다.

문제 분류를 열어보니 dp가 써있었는데 이건 어떻게 해야할지 모르겠다…

---

메모리: 14464KB

시간: 140ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {
    static class Gate {
        int flux;
        int cost;

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

    static int n, v, t, 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());
            t = Integer.parseInt(st.nextToken());
            min = Integer.MAX_VALUE;
            combination(0, 0, 0, 0);

            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, int visit) {
        if (sum >= v) {
            int tmp = 0;
            for (int i = 0; i < n; i++) {
                if ((visit & (1 << i)) > 0) {
                    tmp += arr[i].cost;
                }
            }

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

        if (cnt == n) {
            return;
        }

        for (int i = start; i < n; i++) {
            if ((visit & (1 << i)) == 0) {
                combination(cnt + 1, i + 1, sum + arr[i].flux * t, (visit | (1 << i)));
            }
        }
    }

}