본문 바로가기

알고리즘 관련/BOJ

BOJ)7579 앱

문제: icpc.me/7579


최소한의 비용을 사용하여 m만큼의 메모리를 얻을 때 비용을 출력하는 문제이다.


dp[pos][cost]= pos번째 앱까지 cost만큼의 비용을 사용해 얻을 수 있는 메모리의 최댓값으로 정의 한 뒤


파라메트릭 서치를 이용하여 cost값을 조정해주면 된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, cost, m[101], c[101], dp[101][10001];
int func(int pos, int cos) {
    if (pos < 0)return 0;
    int &ret = dp[pos][cos];
    if (ret != -1)return ret;
    ret = func(pos - 1, cos);
    if (cos - c[pos] >= 0)
        ret = max(ret, func(pos - 1, cos - c[pos]) + m[pos]);
    return ret;
}
int main() {
    scanf("%d%d"&n, &cost);
    int lo = 0, hi = 0;
    for (int i = 0; i < n; i++)
        scanf("%d"&m[i]);
    for (int i = 0; i < n; i++) {
        scanf("%d"&c[i]);
        hi += c[i];
    }
    memset(dp, -1sizeof(dp));
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (func(n - 1, mid) >= cost)
            hi = mid;
        else
            lo = mid + 1;
    }
    printf("%d\n", lo);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1826 연료 채우기  (0) 2017.04.06
BOJ)2056 작업  (0) 2017.04.06
BOJ)2157 여행  (0) 2017.04.05
BOJ)2618 경찰차  (2) 2017.04.05
BOJ)2688 줄어들지 않아  (0) 2017.04.04