[JAVA]백준 1102번: 발전소

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

1102번: 발전소

1. 문제 설명

 

고장 나 있지 않은 발전소를 이용해서 고장 난 발전기를 가동할 수 있다.

 

적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

2. 풀이

 

dp와 비트마스킹을 이용해서 풀 수 있다.

 

현재 켜져있는 발전소 상태를 bit로 표현한다면 아래와 같이 dp로 구현할 수 있다.

 

현재 꺼져 있는 발전소 X가 있다면 현재 켜져 있는 발전소들 중 X를 키는 비용이 최소인 발전소 Y로 X를 켜고, bit에 X가 켜진 것을 반영, 다음 작업을 수행하면 된다.

 

dp를 사용할 때 주의할 점은 음수로 초기화를 해야 한다는 것이다.

 

비용이 음이 아닌 정수이기 때문에 0이 포함된다.

 

따라서 초기화를 하지 않거나 0으로 초기화하게 된다면 시간 초과가 발생할 수 있다.

 

 

3. 코드

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.logging.XMLFormatter;

public class Main {

    public static int num;
    public static int[][] cost;
    public static int P;
    public static int[] dp;
    public static int MAX = 1000;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        num = Integer.parseInt(br.readLine());

        cost = new int[num][num];

        dp = new int[1 << num];


        for (int x = 0; x < num; x++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int y = 0; y < num; y++) {
                cost[x][y] = Integer.parseInt(st.nextToken());
            }
        }

        for (int x = 0; x < (1 << num); x++) {
            dp[x] = -1;
        }

        String status = br.readLine();

        P = Integer.parseInt(br.readLine());

        int bit = 0;
        int on = 0;

        for (int x = 0; x < num; x++) {
            if (status.charAt(x) == 'Y') {
                bit |= 1 << x;
                on++;
            }
        }

        int ans = onFactory(bit, on);


        if (ans == MAX) {
            ans = -1;
        }

        bw.write(String.valueOf(ans));
        bw.flush();


    }

    public static int onFactory(int bit, int onNum) {
        if (onNum >= P) {
            return 0;
        }

        if (dp[bit] != -1) {
            return dp[bit];
        }


        int ret = MAX;

        for (int x = 0; x < num; x++) {
            if ((bit & (1 << x)) == 0) {

                int nextbit = bit | (1 << x);

                int min = MAX;

                for (int y = 0; y < num; y++) {
                    if ((bit & (1 << y)) != 0) {
                        min = Math.min(min, cost[y][x]);
                    }
                }

                ret = Math.min(ret, onFactory(nextbit, onNum + 1) + min);
            }
        }

        dp[bit] = ret;

        return ret;
    }

}

2시간의 고통...