백준 Gold 3 앱

앱 (백준 Gold 3)

https://www.acmicpc.net/problem/7579

앱에 대한 정보 개수 n과 얻어야 하는 바이트 수 m이 주어지고
n에 대하여 해제 시, 얻을 수 있는 바이트 수와 비용이 각각 주어질때

m 이상의 바이트 수를 얻기 위한 최소 비용을 구하는 문제

풀이 방법

비용을 기준으로 바이트 수에 대하여
dp를 적용하면 풀 수 있는 문제이다

• dp[i] : i의 비용으로 얻을 수 있는 최대 메모리 양
  

• dp[i] = max(dp[i],dp[i - w[i]] + v[i]);
  

  전형적인 0/1 배낭 문제 형식의 점화식
  

• 이후 문제의 조건에 따라서 m 메모리 이상을 얻기 위해
  i를 증가시키며 m 이상인지를 체크
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<long long> weights, vals;
	int maxV = 0;

	for (int i = 0; i < n; i++)
	{
		long long w;
		cin >> w;
		weights.push_back(w);
	}

	for (int i = 0; i < n; i++)
	{
		int v;
		cin >> v;
		vals.push_back(v);
		maxV += v;
	}

	// 특정 수치값을 비활성화했을때 얻을 수 있는
	// 메모리의 양
	// dp[i] : i만큼 비활성화 하였을때 얻을 수 있는 최대 메모리 양
	vector<long long> dp(maxV + 1, 0);
	dp[0] = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = maxV; j >= vals[i]; j--)
		{
			dp[j] = max(dp[j], dp[j - vals[i]] + weights[i]);
		}
	}

	for (int i = 0; i <= maxV; i++)
	{
		if (dp[i] >= m)
		{
			cout << i;
			break;
		}
	}

	return 0;
}

결과

처음에 vals와 weight에 대한 판별을 잘못한 것도 있고(변수명을 거꾸로 적용했다)
dp의 개념을 제대로 잡지 못하여 예외처리를 제대로 하지 못하였다

그래도 dp를 명확히 세우고 다시 접근하니
제대로 풀 수 있었다