[BOJ/7579] 앱

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/7579

7579번: 앱

 

2) 설명

 각각의 프로세스가 메모리를 m_i만큼 사용하고 있고, 각 프로세스를 비활성화시킬 때 드는 비용이 c_i라면, 최소 M만큼의 메모리 공간을 확보하는 데 필요한 최소 비용을 구하는 문제

2. 풀이

1) 알고리즘

    : DP(배낭)

 

2) 풀이 설명

 A) 첫 시도 : 2차원 배열 사용하기

    - 처음에는 메모리 생각을 안 하고 100(N 최댓값) x 10000000(M 최댓값) 2차원 배열을 사용했다.

     메모리 초과가 나서 안 되니까 map을 사용해보자는 생각으로 map을 사용했지만 역시나 메모리 초과로 실패했다.     (어차피 사용량 많아지면 비슷해지는 것 같다)

 

 B) 두번째 시도 : 1차원 배열 사용하기

     - 한참 고민하다가 결국 다른 사람들 풀이를 참고해서 풀게 되었다.

      dp 배열 : 1차원 배열로 dp[cost] : cost를 사용해서 최대로 확보할 수 있는 memory

     이제 이중 반복문을 통해 dp 배열을 업데이트해나갔다.

     점화식 : dp[j] = max(dp[j], dp[j - C[i]] + A[i])

      i번째 프로세스를 비활성화할 경우 dp 배열을 업데이트 해나가는 점화식이다.

      만약 활성화된 채로 두는 게 더 큰 memory를 확보할 수 있다면 dp[j] 가 선택 될 것이고, 비활성화하는 게 더 큰 메모리를 확보할 수 있다면 dp[j-C[i]] + A[i] 가 선택될 것이다.

 

3. 코드

/*
	앱
	DP
    1차원 배열을 사용한 풀이
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

#define N_MAX 100
#define C_MAX 100
#define M_MAX 10000000

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, maxCost, answer;
	vector<int> A(N_MAX, 0), C(N_MAX, 0);
	vector<int> dp(N_MAX*C_MAX + 1, 0);

	cin >> N >> M;
	
	for(int i=0;i<N;i++) cin >> A[i];
	for(int i=0;i<N;i++) cin >> C[i];
	
	maxCost = accumulate(C.begin(), C.end(), 0);
	
	for(int i=0;i<N;i++)
		for(int j=maxCost;j>=C[i];j--)
			dp[j] = max(dp[j], dp[j - C[i]] + A[i]);

	for(answer=0;answer<maxCost && dp[answer]<M;answer++);
	cout << answer << "\n";
}

 

/*
	앱
	DP
    vector와 map을 중첩하여 사용한 풀이
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

#define N_MAX 100
#define C_MAX 100
#define M_MAX 10000000

using namespace std;

int N, M;
vector<int> A(N_MAX, 0), C(N_MAX, 0);
vector<map<int, int>> dp(N_MAX);

int solve(int idx, int needMemory){
	if(idx >= N)
		return M_MAX;	
	if(needMemory <= 0)
		return 0;

	if(dp[idx][needMemory] <= 0)
		dp[idx][needMemory] = min(solve(idx + 1, needMemory), C[idx] + solve(idx + 1, needMemory - A[idx]));

	return dp[idx][needMemory];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	
	for(int i=0;i<N;i++) cin >> A[i];
	for(int i=0;i<N;i++) cin >> C[i];

	cout << solve(0, M) << endl;
}

 

4. 느낀점

1) 좀 더 다방면의 방법을 생각해야겠다. 너무 N, M 값에만 집중해서 생각하다보니 다른 방법을 잘 못 찾았다.