7579 앱

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    int app[101] = { 0 };
    int cost[101] = { 0 };
    for (int i = 1; i <= n; i++)
        scanf("%d", &app[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &cost[i]);
 
    // dp[cost] = memory
    int dp[10001] = { 0 };
    for (int i = 1; i <= n; i++) {
        int mem = app[i];
        int c = cost[i];
        
        for (int j = 10000; j > 0; j--)
            if (dp[j] > 0)
                dp[j + c] = max(dp[j + c], dp[j] + mem);        
        dp[c] = max(dp[c], dp[0] + mem);
    }
 
    int minCost;
    for (int i = 1; i <= 10001; i++) 
        if (dp[i] >= m) {
            minCost = i;
            break;
        }
    
    printf("%d", minCost);
}

1. dp[cost] = 최대 memory 양

>> 이 배열을 떠올리지 못했다.

대체 어떻게 이런 생각을 해내는거지?

2. 어찌됐든, 저 발상을 가지고 시작하면 그나마 수월하다

메모장에 하나씩 써보면, 결국 그 전의 어플리케이션 기록을 기반으로 dp를 갱신해야 된다는 것을 알게 된다

3. 또한, 매 턴마다 해당 어플을 비활성화 할 수도, 안 할 수도 있다

4. 위의 매커니즘을 모두 고려해서 하려면, 결국 이중 for 문이 필요하다

5. j=1 에서부터 10000 까지 오름차순으로 갱신하려 했더니, 중복되어 계산되는 경우가 발생함을 알 수 있다.

>> 따라서, 10000부터 1까지 내림차순으로 dp 를 갱신해야겠다는 생각을 하게 된다.