#7579 앱

# 문제

 

# 입력 및 출력

 

# 풀이

처음엔 이렇게 생각해서 그냥 정렬 알고리즘 써서 해도 될 것 같았다,,ㅋㅋ

그래서 아래처럼 작성해서 채점해봤는데

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
int c[100], m[100];

typedef struct {
	int m;
	int c;
}app;

vector<app>app_list;

bool compare(app a, app b) {
	if (a.c == b.c) {
		return a.m > b.m;
	}
	else {
		return a.c < b.c;
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> m[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> c[i];
	}
	for (int i = 0; i < N; i++) {
		app_list.push_back({ m[i],c[i] });
	}
	sort(app_list.begin(), app_list.end(), compare);

	int sum_m = 0, sum_c = 0;
	int i = 0;
	while (sum_m < M) {
		sum_m += app_list[i].m;
		sum_c += app_list[i].c;
		i++;
	}
	cout << sum_c;

	//for (int i = 0; i < N; i++) {
	//	cout << "c: " << app_list.at(i).c << " m: " << app_list.at(i).m << "\n";
	//}
}

시간 초과도 아니고 그냥 답이 다르게 나오는 것 같다

 

예전에 dp, 배낭 문제 풀었을 때 처럼 점화식으로 풀어야 할 듯 하다

 

앞의 평범한 배낭문제를 참고해서 점화식을 작성했음

dp[i][j]=max(dp[i-1][j], dp[i-1][j-c[i]]+m[i])

dp 배열엔 메모리 차지 m값의 합이 들어감

 

dp배열의 j값이 시간(c값)이 되며 dp배열 값인 m의 합이
필요한 메모리 값인 M값보다 크거나 같게 되면 그 때의 c 값을 받아옴

 

코드는 아래 블로그 참고

http://www.systemrequirementslab.com/cyri/

Requirements Test

#include <iostream>
using namespace std;

int mc[2][101];
int dp[101][10001];
int N, M;
int result=1000000000;

int main() {
	cin >> N >> M;
	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> mc[i][j];
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 10001; j++) {
			if (j >= mc[1][i]) {
				dp[i][j] = max(dp[i - 1][j], dp[i-1][j - mc[1][i]] + mc[0][i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
			if (dp[i][j] >= M)
				result = min(result, j);
		}
	}
	cout << result << endl;
}

 

dp문제 많이 풀어야겠다,,ㅋㅋㅋㅋ 넘 어렵다ㅜㅜ