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