[백준] 7579 앱

문제 주소 : www.acmicpc.net/problem/7579

7579번: 앱

문제 확인

 

정렬 후 최선의 선택을 하는 Greedy 알고리즘으로는 예외가 있는 문제를 해결할 수 없습니다. 

memory : 30 10 50

cost       : 2   3   4

위와 같은 경우 확보해야 할 메모리가 40인 경우 cost가 적은 2개를 선택하게 되면 잘못된 답이 될 수 있습니다.

따라서 dp로 풀어야 합니다.

 

풀이

 

cost의 크기가 작기 때문에 인덱스로 활용할 수 있어 사용할 앱 : i, cost : j, 확보한 메모리 : dp[j] 으로 두고 점화식을 세웁니다.

현재 선택한 앱이 i일 때 dp[j] = max(dp[j], dp[j - cost[i]] + memory[i] 가 되며 완전 탐색을 하고 각 스텝에서 확보한 메모리가 m 이상인 경우 cost를 비교해 최솟값을 찾아냅니다.

주의해야 할 점은 dp배열을 1차원으로 사용할 시 dp[j - cost[i]] 값을 활용하기 때문에 충돌을 피해 dp[j] 값을 찾기 위해서는 j를 10000부터 cost[i] 까지 내려가면서 탐색을 해야 합니다.

 

코드

#include <cstdio>
#define max(a,b) a>b ? a : b
int main() {
    int n, m, ans = 0x7fffffff;
    int mem[100], cost[100], dp[10001] = { 0 };
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &mem[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &cost[i]);
    for (int i = 0; i < n; i++) {
        for (int j = 10000; j >= cost[i]; j--) {
            dp[j] = max(dp[j], dp[j - cost[i]] + mem[i]);
            if (dp[j] >= m && j < ans)ans = j;
        }
    }
    printf("%d", ans);
}