[문제해결을 위한 창의적 알고리즘] 앱 (고급 p.112)

이 문제는 배낭 문제와 비슷해 보이지만, 메모리 제약상 테이블을 크게 만들 수 없는 경우 어떻게 해결할 수 있는지 보여주는 문제이다. 해설에 자세하게 설명되어 있으므로 추가적인 설명은 생략하기로 한다. 다이나믹 테이블을 어떻게 채워나가는지 보면 보다 이해가 쉬울 것 같다.

import java.util.Scanner;

public class App112 {

public static int n;

public static int M;

public static int[] mem = new int[101];

public static int[] cost = new int[101];

public static int[][] dt = new int[101][10001];

public static int max(int a, int b){

return a > b ? a : b;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

M = sc.nextInt();

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

mem[i]=sc.nextInt();

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

cost[i] =sc.nextInt();

sc.close();

// 비용 곱하기 앱 숫자는 최대 1만이므로 1 더 큰 값으로 설정

int ans = 10001;

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

for (int j=0; j<=n*100; j++){

// 앱을 끌 수 있는 비용이 허락된다면 해당 앱을 끌 경우와 그렇지 않을 경우의 비용을 비교하여 최대값으로 채운다

if (cost[i]<=j)

dt[i][j]=max(dt[i-1][j], dt[i-1][j-cost[i]]+mem[i]);

else

dt[i][j]=dt[i-1][j];

if (dt[i][j]>=M && j <=ans)

ans = j;

}

}

System.out.println(ans);

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

for (int j = 0; j<=15; j++)

System.out.print(dt[i][j]+" ");

System.out.println("");

}

*/

return;

}

}

Big O(n*c): n은 앱 숫자, c는 비용 합

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

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

출처: 한국정보올림피아드 (2013 지역본선 고등부)