백준 1311번: 할 일 정하기 1

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

N명의 사람이 N개의 작업을 각각 1개씩 처리할 때 필요한 비용이 주어진다. 모든 일을 처리하는데 드는 최소 비용을 출력하는 문제이다.

N이 20개 까지 주어지며, 사람들이 순서대로 남아있는 작업을 선택할 때, 경우의 수를 전부 계산하지 않고 DP를 이용하여 특정 작업들이 이미 선택 되어있는 경우의 비용을 저장하고 또 방문할 경우 다시 선택하지 않고 저장된 비용을 이용한다. 이를 위해  선택된 작업을 저장하는 비트마스킹이 필요하다.

 

필수적인 작업만 하기 위해 1부터 2^n까지 반복하는 것이 아닌 재귀를 사용하였다. 제귀 함수 내에서 bits는 선택된 작업 정보를 비트마스킹 하였으며, start는 현재 작업을 선택할 직원의 번호이다. 현재 상황에서 가능한 선택지 중 최소의 비용을 구하고 DP에 저장한 후 반환하였다.

private static int dp(int bits, int start) {
    if (start == n) {
        return 0;
    }
    if (dp[bits] != 0) {
        return dp[bits];
    }
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        if ((bits & 1 << i) == 0) {
            int value = board[start][i];
            int newBits = bits;
            newBits |= 1 << i;
            value += dp(newBits, start + 1);
            min = Math.min(min, value);
        }
    }
    return dp[bits] = min;
}

 

결과 코드는 다음과 같다.

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

public class 할일정하기1 {
    
    static int[][] board;
    static int[] dp;
    static int n;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        dp = new int[1 << n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.print(dp(0, 0));
    }
    
    private static int dp(int bits, int start) {
        if (start == n) {
            return 0;
        }
        if (dp[bits] != 0) {
            return dp[bits];
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if ((bits & 1 << i) == 0) {
                int value = board[start][i];
                int newBits = bits;
                newBits |= 1 << i;
                value += dp(newBits, start + 1);
                min = Math.min(min, value);
            }
        }
        return dp[bits] = min;
    }
}