[BOJ] 7579 앱

DP 문제인데, 정말 진땀 뺀 문제이다. 

단순히 메모리의 크기를 index로 잡기엔 값이 너무 커서, cost를 인덱스로 잡아서 풀었다.

배열에 저장되는 값은 해당 cost로 얻을 수 있는 최대 Memory 이득이다. 

포인트는 이부분이다. 순방향이 아니라 역방향으로 진행해야 메모리가 중복해서 사용되는 것을 방지할 수 있다.

 

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int N, M, temp;
int c[101];
int m[101];
int dp[10001];

int main(){
  scanf("%d %d", &N, &M);

  for(int i = 0 ; i < N ; i++){
    scanf("%d", &m[i]);
  }

  for(int i = 0 ; i < N ; i++){
    scanf("%d", &c[i]);
  }

  for(int i = 0 ; i < 10001; i++){
    dp[i] = INT_MIN;
  }

  dp[0] = 0;

  for(int i = 0 ; i < N ; i++){
    for(int j = 10000; j >= 0; j--){
      if(j - c[i] < 0){
        continue;
      }
      dp[j] = max(dp[j - c[i]] + m[i], dp[j]);
    }
  }

  for(int i = 0 ; i < 10001; i++){
    if(dp[i] >= M){
      printf("%d", i);
      break;
    }
  }

  return 0;
}