[C++] 7579 앱 - DP, 배낭 문제

#include <iostream>
#include <algorithm>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 101
#define MAX_M 10000001
#define MAX_C 100*100+1

using namespace std;

int N, M;  //앱의 개수 N, 확보해야하는 바이트의 수 M
int me[MAX_N], co[MAX_N];  //차지하고 있는 메모리의 크기와, 가치
int sumM, sumC;
int map[MAX_N][MAX_C];

void input()
{
    cin >> N >> M;
    LOOP(i, N) cin >> me[i];
    LOOP(i, N) cin >> co[i];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    LOOP(i, N) {
        int W=me[i], C=co[i];
        for(int j=C; j<=MAX_C; j++) {
            if(j-C>=0)
                map[i][j] = max(map[i-1][j-C]+W, map[i-1][j]);
            else
                map[i][j] = map[i-1][j];
        }
    }
    
    LOOP(i, MAX_C) {
        if(map[N][i]>=M) {
            cout << i;
            break;
        }
    }
    
    return 0;
}

일단 기존 배낭문제와 매우 비슷하다고 느꼈는데 M의 범위를 보고 많이 놀랐다.

 

<시행착오>

1. M가지고 배낭문제를 적용하려고 했다가 메모리문제로 혼났다. C로 배낭 알고리즘을 적용시키자.

 

2차원 배열을 안쓰고 1차원 배열에 조금 더 빠른 코드를 사용한 사람이 있어서 가져왔다.

 

<참고 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/31043307

로그인

애초에 j-C>=0인 영역만 탐색함으로써 일차원 배열로 갱신할 수 있도록 구현되어있다.

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.