시작

이 문제는 Dynamic Programing을 이용해 풀면 되는 문제다. 그렇담 어떻게 해야되는지를 알아야되는데, 우선 어떻게 제작을 해야되는지부터 알아야된다. 한번 간단하게 설명을 해보면 예시 반례로 한번 설명을 해보자면

앱의 개수는 6개, 원하는 메모리 감소는 60 그렇다면 지금 6개의 메모리 차지값과, 앱을 끄면 사용하는 메모리를 알 수 있는데, 이건, 앱을 끄거나, 안끄거나, 또는 앱을 다시 켜서 다른걸 끄가나를 알면 된다. 그렇다면 DP의 특성인 점화식을 찾으면 되는 문제

이런식으로 해결하면 된다고 한다. 그러면 한번 알고리즘을 간단하게 짜보자.

알고리즘

1. 넣을 수 있는지 없는 지 확인 후 넣을 수 있으면 넣기
2. 못 넣으면 다른걸 빼고 넣을 수 있는지 확인
3. 넣을 수 있으면 빼고, 넣어서 확인

코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>

using namespace std;

int N, M, minNum = 214785154;
vector<int> A, C;
vector<int> arr(100001);;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> M;
	A.resize(N);
	C.resize(N);
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 100 * N - 1; j >= 0; j--) {
			if (j >= C[i]) {
				arr[j] = max(arr[j], arr[j - C[i]] + A[i]);
			}	
			if (arr[j] >= M) {
				minNum = min(minNum, j);
			}
		}
	}
	int value = count(C.begin(), C.end(), 0);
	if (value == N) {
		cout << 0;
	}
	else {
		cout << minNum;
	}
}