앱

백준 7579번: 앱

아이디어

맨 처음 계획한 풀이는 배열의 인덱스를 지금까지 확보한 메모리로 하고, 그 값은 메모리를 확보하는데 필요한 최소한의 비용으로 해서 풀려고 했는데 메모리가 천만이라 실패했다.
발상의 전환으로, 배열의 인덱스를 지금까지 사용한 비용으로 하고, 그 값은 해당 비용으로 확보할 수 있는 최대한의 메모리로 했다. 그리고 그 중에서 처음으로 값이 M보다 커지는 인덱스를 찾으면 정답이다.

DP테이블엔 이렇게 적힌다. (문제에서 준 예제)

코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
int mem[100];
int c[100];
int dp[100][10001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> mem[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> c[i];
    }

    int ans = 10001;
    for (int i = c[0]; i < 10001; i++) {
        dp[0][i] = mem[0];
    }
    if (mem[0] >= M) ans = c[0];  
       
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < 10001; j++) {
            if (j < c[i]) {
                dp[i][j] = dp[i-1][j];
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+mem[i]);        
            }
            if (dp[i][j] >= M) {
                ans = min(ans, j);
            }
        }
    }
    cout << ans;
    return 0;
}

여담

아니 이거 메모리 천만인데 어떻게풀어? 하고 한참을 삽질했다.
안될거같으면 빠르게 발상을 전환해보자. 솔직히 발상을 전환하라는게 말이쉽지 많이 안풀어봤으면 두들겨 맞기 딱 좋은 문제임 ㅋㅋ;