[문제해결을 위한 창의적 알고리즘] Minimum Sum (고급, p200)
이 문제는 비트 오퍼레이션을 통해 보다 빠르게 동작하는 방법을 알아보는 문제이다. 역시 동적계획법을 통해 문제를 푸는 방법을 알아본다. 비트 연산을 어떻게 적용하는지 알아두는 것이 핵심이라고 할 수 있겠다.
import java.util.Scanner;
public class MinSumSol205 {
// 최대값 설정
public static final int INF = 987654321;
// 입력 받을 공간
public static int[][] m = new int[21][21];
public static int bit, n;
// 동적 테이블 선언
public static int[] DT = new int[1<<20];
public static void input(){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++)
for (int j = 0; j< n; j++)
m[i][j]=sc.nextInt();
sc.close();
return;
}
public static int min(int a, int b){
return a > b ? b : a;
}
public static int f(int row, int bit){
if (row==n)
return 0;
// 만약 동적 테이블이 한번도 업데이트되지 않았다면
if (DT[bit]==0){
// 최대값으로 업데이트 하고
DT[bit]=INF;
for (int i = 0; i < n; i++)
// 한번도 사용하지 않은 열이면
if ((bit&(1<<i))==0)
// 현재 행의 선택한 열값과 최대값 중 작은 값으로 업데이트 한다
DT[bit]=min(DT[bit], f(row+1, bit+(1<<i))+m[row][i]);
}
return DT[bit];
}
public static void main(String[] args){
input();
System.out.println(f(0,0));
return;
}
}
Big O(n^2)
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/MinSumSol205.java