BOJ - 앱(7579)

문제(링크)

풀이:
12865번 평범한 배낭 문제와 같은 냅색 문제였습니다.

냅색 문제에서
배낭의 무게 = 비용,
물건의 가치 = 메모리
로 바꾸어 풀이하면 됩니다.

가치(메모리)가 M 보다 크거나 같을 때 비용을 출력하고 종료합니다.

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#include<queue>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>

int N, M;
int dp[10001][101];
int mem[101];
int cost[101];

int main(void) {
 FIO;

 cin >> N >> M;

 for (int i = 1; i <= N; i++)
 {
  cin >> mem[i];
 }
 for (int i = 1; i <= N; i++)
 {
  cin >> cost[i];
 }

 for (int i = 0; i <= 10000; i++)
 {
  for (int j = 1; j <= N; j++)
  {
   if (cost[j] <= i) {
    dp[i][j] = max(dp[i][j - 1], dp[i - cost[j]][j - 1] + mem[j]);
   }
   else {
    dp[i][j] = dp[i][j - 1];
   }
   if (dp[i][j] >= M) {
    cout << i;
    exit(0);
   }
  }
 }
}