[백준 7579] 앱 [C]

백준 - 7579

---

풀이

입력받은 비용들의 총 합을 구해주고, 비용별로 확보할 수 있는 메모리의 최댓값을 구해야 한다.

for (int i = 0; i < N; i++)
    for (int cost = sum; cost >= c[i]; cost--)
        dp[cost] = max(dp[cost], dp[cost-c[i]] + m[i]);

그 후 입력받은 M만큼의 메모리 이상을 확보하는 비용을 찾아 출력하면 된다.

---

소스코드

#include <stdio.h>
#define MAX 101
#define max(a, b) a > b ? a : b
int c[MAX], m[MAX], dp[10001];
int main(){
    int N, M;
    scanf("%d %d", &N, &M);
	
    for (int i = 0; i < N; i++)
        scanf("%d", &m[i]);
	
    int sum = 0;
    for (int i = 0; i < N; i++){
        scanf("%d", &c[i]);
        sum += c[i];
    }
	
    for (int i = 0; i < N; i++)
        for (int cost = sum; cost >= c[i]; cost--)
            dp[cost] = max(dp[cost], dp[cost-c[i]] + m[i]);
			
    for (int cost = 0; cost <= sum; cost++)
        if (dp[cost] >= M){
            printf("%d", cost);	
            break;
        }
}

---

출처

7579번: 앱