[백준] 1311번 할 일 정하기1

문제 설명

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

문제 풀이

• 우선 bruteforce로 풀기에는 20!의 경우의 수가 나오므로 불가능하다.
• 비트마스킹을 이용한 DP를 이용하여 풀이하였다.
• DP테이블 정의는 다음과 같다.

  DP[현재까지 선택한 일의 조합][현재 사람 번호] : 현재 사람까지 특정 조합의 일을 선택했을 때 최소 비용

• 위 정의를 사용했을 때 결과는 DP[(1<<N)][N-1]이 된다.

소스 코드 (JAVA) - for문

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

class Main {

    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int INF = 987654321;

    public static int N;          // 사람수
    public static int[][] map;    // 사람별 일할때 필요한 비용

    public static int[][] dp;

    public static void solve() throws IOException {
        //0번 사람의 경우 초기화
        for (int i = 0; i < N; i++)
            dp[0][1 << i] = map[0][i];
        //1번 사람부터 N-1번 사람까지 계산
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 1 << N; j++) {
                if (dp[i-1][j] == INF) continue;  //직전까지 조합이 성립 안되는 경우 제외

                for (int k = 0; k < N; k++) {
                    if ( (j & (1 << k)) != 0) continue; //이미 했던 일이라면
                    dp[i][j | (1 << k)] = Math.min(dp[i][j | (1 << k)], dp[i-1][j] + map[i][k]);
                }
            }
        }
        bw.write(dp[N-1][(1 << N) - 1] + "\n");
        bw.flush();
    }

    public static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[N][1 << N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], INF);
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }


}

소스 코드 (JAVA) - recursive

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

class Main {

    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int N, INF = 987654321;
    public static int[][] map;
    public static int[][] dp;

    // ind번 사람까지 select(비트마스킹)일를 선택했을 때 비용의 최소값
    public static int solve(int select, int ind) {
        //기저조건1
        if (ind == -1) return 0;
        //기저조건2
        if (dp[select][ind] != INF) return dp[select][ind];
        //하나씩 일을 빼면서 이전 경우 확인
        int min = INF;
        for (int i = 0; i < N; i++) {
            //선택 안된 일인 경우 넘김
            if ((select & (1<<i)) == 0) continue;
            min = Math.min(min, solve(select - (1<<i), ind-1) + map[ind][i]);
        }
        return dp[select][ind] = min;
    }

    public static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[1<<N][N];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < (1<<N); i++)
            Arrays.fill(dp[i], INF);
    }

    public static void main(String[] args) throws IOException {
        input();
        bw.write(solve((1<<N) - 1, N-1) + "\n");
        bw.flush();
    }
}