2013 한국정보올림피아드 시.도지역본선 고등부 4번 앱(BOJ: 7579) 풀이

분류 : 다이나믹프로그래밍

 

이 문제는 냅색의 기본이론과 다른 방식으로 테이블을 작성해야 합니다. 냅색의 기본이론은 가로축이 책가방의 크기(사용할 수 있는 전체 크기) 입니다. 그리고 테이블 속의 데이터는 취할 수 있는 이득입니다.

 

하지만 이문제에서 비용의 범위가 10,000,000이며 개수가 100개이므로 최대 10억 개의 데이터를 채워야 합니다. 시간복잡도와 공간복잡도를 고려한 접근이 필요합니다.

냅색은 가로축이 크기이고 내용이 얻는 비용입니다.

이것을 역으로 생각해서 가로축을 비용, 내용을 크기로 해봅시다. 그럼 어떤 비용에서 최대 크기를 구할 수 있습니다.

5 60 30 10 20 35 40 3 0 3 5 4

Input이 위와 같을 때

그럼 위와 같이 표를 채울 수 있습니다. 가장 아래쪽 라인에서 60을 최초로 넘는 지점의 가로축 값이 60을 만들 수 있는 최소한의 누적 C입니다. 그래서 답은 6이 됩니다.

#include <stdio.h>
int mem[100];
int cost[100];
int dp[100][20000];
int main() {

	int N, M;
	int sum = 0;
	//freopen("Text.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d", &mem[i]);
	}
	for (int i = 0; i < N; i++) {
		scanf("%d", &cost[i]);
		sum += cost[i];
	}
	for (int i = cost[0]; i <= sum; i++) {
		dp[0][i] = mem[0];
	}
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < cost[i]; j++) {
			dp[i][j] = dp[i - 1][j];
		}
		for (int j = cost[i]; j <= sum; j++) {
			dp[i][j] = (dp[i - 1][j - cost[i]] + mem[i]) > (dp[i - 1][j]) ? (dp[i - 1][j - cost[i]] + mem[i]) : dp[i - 1][j];
		}
	}
	int min;
	for (int i = 0; i <= sum; i++) {
		if (dp[N - 1][i] >= M) {
			min = i;
			break;
		}
	}
	printf("%d\n", min);
	return 0;	
}