[BaekJoon][7579] 앱

BAEKJOON ONLINE JUDGE

7579 앱

https://www.acmicpc.net/problem/7579

DP!

최소의 비용

문제의 핵심은 입력 메모리 값을 적절히 조합하여 합이 필요한 메모리 M 이상을 만드는데, 그 중 cost가 가장 작은 값을 출력하는 것이다.

단순히 완전히 탐색을 하여 메모리 조합을 찾는 경우에는 당연히 Time Limit가 발생한다.

따라서 DP로 문제를 풀어야 하는데

처음에는 dp[메모리] = cost(최소값) 로 생각을 하여

dp의 index(memory)가 입력 기준을 처음으로 넘는 cost를 출력하려 하였으나 메모리 범위가 넓어 배열을 잡을 수 없다.

---> 반대로!!

index와 값을 반대로 하여 보자

dp[cost] = memory(최대값)

입력 메모리와 cost를 입력순으로 저장해 놓고

그 순서대로 cost와 메모리를 더해나간다.

즉 첫 번째, 앱을 선택한다, 안한다로 결정할 경우 cost는 0과 3.

--> dp[0] = 0, dp[3] = 30이 저장된다.

두번째, 두번째 앱을 더하거나, 안더하는 경우 cost는 이전에 값이 결정된 0과 3에서 

첫번째 앱이 선택되지 않은 0에서 두번째 앱을 선택하지 않는 cost 0 -> 0과 선택하는 cost 0 -> 10 중 큰 값을 저장한다.

첫번째 앱이 선택된 3에서 두번째 앱을 선택하지 않는 경우 cost 3 -> 30, 선택할 경우 cost 3 -> 40 (이전 30 + 두번째 앱 메모리 10) 중에서 더 큰 값인 40을 저장한다.

이런 식으로 계산을 해 나가 마지막 앱까지 선택을 마친다면 모든 부분 집합의 cost별 최대 memory를 저장 할 수 있다.

이 중 cost를 다시 돌면서 dp에 저장된 비용 별 최대 memory 값 중 필요한 메모리를 처음으로 넘을 때의 cost를 출력하면 된다.

문제는 맞았지만 code를 최적화 하지 않아서 dp를 만드는 부분과 찾는 부분이 나누어져 있는데, 생각해보면 합쳐서 한번에 구현할 수 있을 것 같기도 하다.

#include <stdio.h>
 
int n, m;
int memory[101];
int cost[101];
int dp[10001][100];
int list[10001];
 
void init()
{
    int i, j;
 
    for (i = 0; i < 10001; i++) {
        for (j = 0; j < 100; j++) {
            dp[i][j] = -1;
        }
    }
}
int process()
{
    int i, j, t;
    int c, mem;
 
    dp[0][0] = 0;
 
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= 10000; j++) {
            if (dp[j][i - 1] >= 0) {
                c = j;
                mem = 0;
                for (t = 0; t < 2; t++) {
                    if (dp[j][i - 1] + mem> dp[c][i])    dp[c][i] = dp[j][i - 1] + mem;
                    c = j + cost[i];
                    mem = memory[i];
                }
            }
        }
    }
 
    j = 0;
    while (j <= 10000 && dp[j][n] < m)    j++;
    return j;
}
 
int main() {
    int i;
 
    scanf("%d %d", &n, &m);
 
    init();
 
    for (i = 1; i <= n; i++)        scanf("%d", &memory[i]);
    for (i = 1; i <= n; i++)         scanf("%d", &cost[i]);
 
    printf("%d\n", process());
 
    return 0;
}