[문제해결을 위한 창의적 알고리즘] 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

문제해결을 위한 창의적 알고리즘 목록