[백준 c++] 7579 앱

점화식이 어려운, 냅색(배낭문제, KnapSack) 이라는 유형을 변형한 문제이다.

 

맨 처음 출력/입력 조건을 본다.

문제 내용상 흐름을 파악해봤을 때, N은 100, M은 1억이다. 

완전탐색을 가정했을 때, 활성화됐는지 아닌지 쭉 파악하는 시간복잡도는 on/off 여부를 모두 체크하면 (2^N)이다.

입력값은 1억까지인데, 2^N으로 감당할 수 있는 입력값은 20이므로, 이는 시간복잡도 내에 해결할 수 없다.

=> 따라서 다른 방법을 생각해보자. DP로 해야한다.

 

DP로 하려면 3가지가 필요하다.

1)DP 배열

2)점화식

3)초깃값

 

dp[i][j]에서 i와 j를 뭐라고 생각할지 판단해야한다.

처음에는 i번째에 확보할 수 있는 메모리 j에 드는 비용 cost를 dp[i][j]라고 세웠다. 그런데 이렇게 되면, j의 범위가 1억까지이므로 메모이제이션이 불가능하다.

 

따라서 d[i][j]를 i번째 앱까지, j의 cost로 확보할 수 있는 메모리로 정의한다.

 

m[i]	30	10	20	35	40	비용합계
c[i]	3	0	3	5	4	15

 

실제로 문제 풀 때도 손으로 그려서 파악한다.

d[i][j]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
d[1][j]	0	0	0	30	30	30	30	30	30	30	30	30	30	30	30	30
d[2][j]	10	10	10	40	40	40	40	40	40	40	40	40	40	40	40	40
d[3][j]	10	10	10	40	40	40	60	60	60	60	60	60	60	60	60	60
d[4][j]	10	10	10	40	40	45	60	60	75	75	75	95	95	95	95	95
d[5][j]	10	10	10	40	40	45	60	80	80	85	100	100	115	115	115	135

d[j-1][j-cost[i]+m[i]와 d[i-1][j] 비교

 

와! 점화식이 왜 d[i-1][j-cost[i]] + memory[i] 이런식인가 했더니, 해당하는 비용값을 하나 더하면 당연히 필요로 하는 j값에는 cost[i]만큼 빠진 것이 이제 필요로 되고, 대신 메모리를 얻으니까 이런거다.

 

강사님께서 주신 자바 코드.

package b7579;

import java.util.Scanner;

/*
 * 백준 7579 앱
 * updated 2024-02-17
 */
public class Main2 {
    static int N, M;    // 앱개수, 필요한 메모리
    static int[] m; // 앱 메모리
    static int[] c; // 비용
    static int sum;
    static int[][] d;       // 비용 i번째 앱까지 j 의 비용을 들였을 때 얻을 수 있는 최대 메모리양

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        m = new int[N+1];
        c = new int[N+1];

        for (int i=1; i<=N; i++) {
            m[i] = sc.nextInt();
        }
        for (int i=1; i<=N; i++) {
            c[i] = sc.nextInt();
            sum += c[i];
        }
        d = new int[N+1][sum+1];
        for (int i=1; i<=N; i++) {
            for (int j=0; j<=sum; j++) {
                if (j - c[i] >=0) d[i][j] = Math.max(d[i][j], d[i-1][j-c[i]] + m[i]);
                d[i][j] = Math.max(d[i][j], d[i-1][j]);
            }
        }
        int cost = 0;
        for (int i=1; i<=N; i++)
            for (cost=0; cost<sum && d[i][cost]<M; cost++);
        System.out.println(cost);       
    }

}

 

그리고 C++코드로 변환한 것

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N, M; // 앱 개수, 필요한 메모리;
    cin >> N >> M;
    
    vector<int> m(N+1); // 앱 메모리
    vector<int> c(N+1); //비용
    int sum = 0;
    
    //입력 받는 것 - python과 달리, 미리 공간을 파놓고 입력을 받는다.
    for (int i=1; i<=N; i++){
    	cin >> m[i];
    }
    
    for (int i=1; i<=N; i++){
    	cin >> c[i];
        sum += c[i];
    }
    
    //비용 1번째 앱까지 j의 비용을 들였을 때 얻을 수 있는 최대 메모리양
    vector<vector<int>> d(N+1, vector<int>(sum+1,0));
    
    for (int i=1; i<=N; i++){
    	for (int j=0; j <=sum; j++){
        	if (j-c[i] >=0) {
            	d[i][j] = max(d[i][j], d[i-1][j-c[i]] + m[i]);
            }
            d[i][j] = max(d[i][j], d[i-1][j]);
        }
    }
    
    int cost = sum;
    for (int i=0; i<=sum; i++){
    	if (d[N][i] >= M) {
        	cost = i;
            break;
        }
    }
    
    cout << cost << endl;
    
    return 0;
}