Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

33. 동적 계획법3

비트마스크를 배우고, 동적 계획법에 적용해 봅시다. 그 후에는 선형이 아니라 원형으로 구성된 문제를 다룹니다.

Java / Python

2. 할 일 정하기1

1311번

선택한 열의 상태를 비트마스크로 저장하여 DP를 진행하는 문제

이번 문제는 Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 문제이다.

일의 상태를 비트마스크로 저장하고 각각의 사람과 일의 상태를 매칭시키며 메모이제이션(DP 이용)을 적용하면 되는 방법이라고 한다.

• Java

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

public class Main {
	static final int INF = 99999999;
	static int N;
	static int[][] dp;
	static int[][] cost;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		cost = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		dp = new int[N][1 << N];

		bw.write(DP(0, 0) + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	static int DP(int now, int flag) {
		if (now == N)
			return 0;
		if (dp[now][flag] != 0)
			return dp[now][flag];

		int result = INF;
		for (int i = 0; i < N; i++) {
			if ((flag & (1 << i)) == 0)
				result = Math.min(result, cost[now][i] + DP(now + 1, flag | (1 << i)));
		}
		dp[now][flag] = result;
		return dp[now][flag];
	}
}

• Python (PyPy3)

import sys
input = sys.stdin.readline
N = int(input())
cost = [[*map(int, input().split())] for _ in range(N)]
dp=[10**6]*(1<<N)
dp[0]=0

for i in range(1<<N):
    k = 0
    for j in range(N):
        if i & (1<<j):
            k+=1
    for j in range(N):
        if i & (1 << j) == 0 and dp[i|(1<<j)] > dp[i]+cost[k][j]:
            dp[i|(1<<j)] = dp[i] + cost[k][j]

print(dp[-1])