[백준/C++] 앱

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 풀 때, 냅색 문제와 같이 풀었다.

 

M의 크기를 갖는 배열을 만든 다음 i 만큼의 메모리를 cost를 주고 만들 수 있다면 새롭게 비용을 주고 특정 메모리를 만들 수 있는지 체크했다.

 

이렇게 풀면 통과는 되지만 10,000,000 * 100의 연산을 해야하기 때문에 비효율적 이었다.

 

다른 풀이가 있을까 찾던 중 메모리가 기준이 아니라 cost를 기준으로 하는 풀이가 있었다.

 

DP[N][cost]을 만들고 여기에 메모리를 저장 하는 방법이다.

 

아래 그림을 따라 진행해보자

 

 먼저 처음에 위 그림과 같이 초기화를 한다.

 

이후 첫번째 비용과 메모리를 이용해 Cost를 써서 얼마의 메모리를 만들 수 있는지 DP배열에 저장한다.

만들 수 있는 메모리가 INF값이 아닌 값이 Cost가 0 일 때 발견됐다.

 

그러므로 0 Cost에 3 Cost를 더 쓰면 3 Cost로 30의 메모리를 줄일 수 있다.

 

그리고 0 Cost를 써서 다시 0의 메모리를 만들 수 있으므로 그 값을 저장한다.

(  DP[i-1][cost]가 INF값이 아니면 DP[i][cost]=max(DP[i-1][cost], DP[i][cost])  )

 

그 결과 아래 그림과 같이 값이 채워진다. 

 

 

계속 진행해 3번째 메모리의 경우를 생각해보자

 

3의 Cost를 사용해 줄일 수 있는 메모리가 30과 40이다.

그러므로 Cost 3에는 이 중에 큰값인 40을 저장한다.

 

Cost가 6인 경우에는 메모리를 60 줄일 수 있다.

 

여기서 줄여야하는 메모리인 60과 같으므로 result에 cost 6 저장하면 된다.

(result에는 줄여야하는 메모리의 조건을 충족 할 때, 가장 적은 비용을 저장해 둔다)

 

위 과정을 반복하면서 줄여야하는 메모리 이상의 값이 DP배열에 저장되면, 그때 드는 비용을 result에 저장해 최소값을 출력하면 된다.

 

 

​

[아이디어 정리]

1. DP[i][Cost]를 만들어 줄일 수 있는 메모리의 크기를 저장하는 DP배열을 만든다.
2. DP[i-1][Cost]배열의 값이 INF가 아니라면 DP[i][Cost + i번째 Cost]에 줄일 수 있는 메모리 값 중 가장 큰 값을 저장한다.
3. 만약 저장되는 메모리 값이 줄여야 하는 목표값 M 이상이라면 조건을 충족 했으므로 이때 비용인 Cost + i번째 Cost를 result 값과 비교하고 더 작은 값을 저장한다.
4. 모든 앱의 경우를 비교한 다음 result에 저장된 값을 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = -1;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> vp(N); //메모리, 비용
	vector<int> retAns(M + 1, INF);
	int maxCost=0;
	retAns[0] = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> vp[i].first;
	}
	for (int i = 0; i < N; i++)
	{
		cin >> vp[i].second;
		maxCost += vp[i].second;
	}
	int result = 100000000;
	vector<vector<int>> DP(N + 1, vector<int>(maxCost + 1, INF));
	DP[0][0] = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = maxCost; j >= 0; j--)
		{
			if (DP[i][j] != INF)
			{
				DP[i + 1][j] = max(DP[i + 1][j], DP[i][j]);
				int nCost = j + vp[i].second;
				DP[i + 1][nCost] = max(DP[i + 1][nCost], DP[i][j] + vp[i].first);
				if (DP[i + 1][nCost] >= M)
				{
					result = min(result,nCost);
				}
			}
		}
	}
	cout << result;
	return 0;
}

 

---

DP는 정말 기준을 뭐로 잡느냐에 따라서 문제 효율이 많이 달라지는 것 같다.

DP문제라고 느껴지면 문제 풀기전에 기준에 대한 고민을 더 해볼까...

7579번: 앱