[백준 12920] 평범한 배낭 2 쉬운 풀이

12920번: 평범한 배낭 2

 

시간제한: 1초

메모리제한: 512MB

---

1) 덱을 이용한 DP, 2) 물건의 개수를 2의 지수꼴로 분할해 푸는 것이 일반적인 방법으로 보인다.

그러나 이 두 방법을 사용하지 않고 단순한 배낭문제 아이디어로 $O(N^2M)$ 만에 풀 수 있다.

$N = 100, M = 10000$ 이라고 했을 때 연산 횟수가 약 1억회이고,

아래 코드를 제출하면 약 12ms에 통과한다.

<소스 코드>

#include <cstdio>
int main() {
    int n,m;
    scanf("%d %d", &n, &m);
    int weight[n], value[n], iscontain[m+1][n], maxvalue[m+1];

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &weight[i], &value[i], &iscontain[0][i]);
        for (int j = 1; j < m+1; j++) {
            iscontain[j][i] = iscontain[0][i];
        }
    }
    // O(n*n*m)
    for (int i = 0; i < m+1; i++) {
        maxvalue[i] = 0;
        for (int j = 0; j < n; j++) {
            if (i-weight[j] >= 0) {
                if (maxvalue[i] < maxvalue[i-weight[j]] + value[j] && iscontain[i-weight[j]][j] != 0) {
                    maxvalue[i] = maxvalue[i-weight[j]] + value[j];
                    for (int p = 0; p < n; p++) {
                        iscontain[i][p] = iscontain[i-weight[j]][p];
                    }
                    iscontain[i][j]--;
                }
            }
        }
    }
    int max = 0;
    for (int i = 0; i < m+1; i++) {
        if (maxvalue[i] > max) max = maxvalue[i];
    }
    printf("%d", max);
}

<코드 설명>

$iscontain[m+1][n]$ : 배낭 무게가 $0 \leq x \leq m$일 때 그 배낭에 더 넣을 수 있는 물건 개수를 저장하는 배열

$maxvalue[m+1]$ : m만큼 돌면서, 배낭의 무게가 $0 \leq x \leq m$일 때 value의 최고값을 저장하는 배열

이런 식으로 $N^2M$ 만큼 돌고 마지막에 $maxvalue$ 배열에서 가장 큰 값을 찾으면 그것이 정답이 된다.