[문제해결을 위한 창의적 알고리즘] 선물 (고급, p178)

이 문제도 이전에 중급에서도 등장했던 문제이다. 그러나 마찬가지로 동적계획법 (Dynamic Programming)으로 풀려고 하면 방법이 잘 생각나지 않는다. 특히 무게의 합을 가지고 다이나믹 테이블을 만든다는 점을 유의해서 풀어야 한다.

아래에서 DT[k][b][c]= 현재 k개의 선물을 받았을 때, 길순이가 부피 b, 길삼이가 부피 c를 받을 수 있으면 1, 그렇지 않으면 0으로 정의한다.

import java.util.Scanner;

public class PresentSol190 {

public static int n, W;

public static int[] G = new int[21];

public static int A, B, C;

public static int ans = 0x7fffffff;

// 직전 단계만 보면 되므로 2로 선언

public static boolean[][][] DT = new boolean[2][668][668];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n= sc.nextInt();

for (int i = 1; i <= n; i++) {

G[i] = sc.nextInt();

W+=G[i];

}

DT[0][0][0] = true;

for (int i = 1; i <= n; i++)

for (int a = 0; a<=667; a++)

for (int b= 0; b<=667; b++)

DT[i%2][a][b]=(DT[(i-1)%2][a][b] ||

(a-G[i]<0?false:DT[(i-1)%2][a-G[i]][b] ||

(b-G[i]<0?false:DT[(i-1)%2][a][b-G[i]])));

for(int a = 0; a <= 667; a++)

for (int b = 0; b <= 667; b++)

if(DT[n%2][a][b]) {

if (W-(a+b)>=a && a>=b &&W-(a+b)-b<=ans){

ans = W-(a+b)-b;

A=W-(a+b);

B=a;

C=b;

}

}

System.out.println(A+" "+B+" "+C);

sc.close();

return;

}

}

Big O(n*W*W): n:선물 개수, W:선물 무게 총합

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/PresentSol190.java

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