본문 바로가기

알고리즘 문제풀이/백준 문제풀이

[BOJ 12920] 평범한 배낭 2

728x90
반응형

[문제] : https://www.acmicpc.net/problem/12920

 

12920번: 평범한 배낭 2

첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 �

www.acmicpc.net

 

[필요 개념]

- DP , 배낭 문제 (Knap-sack)

- 비트마스크

 

[풀이]

전형적인 배낭문제 (Knapsack)처럼 보이나, 이 문제에서는 특별하게 고려해줘야 하는 부분이 있다. 

바로 같은 종류의 물건의 개수가 2개 이상일 수 있다는 것이다. 

원래 배낭문제에서는 각 물건이 하나씩 있어, 해당 물건을 넣거나 빼는 두가지 경우만 있었는데, 이 문제같은 경우에는 물건의 개수가 여러개가 있어서 경우가 훨씬 많아졌다. 

처음에는 같은 종류의 물건들을 모두 다르게 생각해서, dp에 추가해주는 방식을 이용해볼 수 있다.

int dp[10001];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M; cin >> N >> M;

    for (int i = 0; i < N; i++) {
        int v, c, k; cin >> v >> c >> k;

        while (k--) {
            for (int j = M; j >= v; j--) {
                dp[j] = max(dp[j - v] + c, dp[j]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= M; i++) ans = max(dp[i], ans);
    cout << ans;
}

 

위의 코드는 k개의 같은 종류의 물건들을 하나씩 dp에 저장해주는 과정이다.

이 방식을 이용하게 되면 물론 시간초과가 발생하게 된다. 물건 한 종류당 최대 10000개가 존재할 수 있으므로, V = 1, M = 10000, K = 10000이 되면 while문이 1억번 돌게 된다. 

그렇다면 어떻게 해야할까? 핵심 아이디어는 2진수 비트(bit)를 이용하는 것이다. 

예를 들어서 한 물건을 7개 담은 경우를 생각해보자. 위의 방식대로라면 물건을 하나씩 추가하면서 dp를 갱신하므로 총 7번 반복하게 된다. 

하지만, 7은 1 + 2 + 4 이므로, 1개를 더 추가한 경우와, 2개를 더 추가한 경우, 4개를 더 추가한 경우 모두 dp에 갱신을 시키면 결국 7개가 추가된 경우가 자동으로 갱신이 된다. 

이런 방식으로 물건을 1개씩 추가하는 것이 아니라, 2의 거듭제곱씩 추가하게 되면 모든 수를 다 고려할 수 있게 된다. 

모든 자연수는 2의 거듭제곱의 합으로 나타낼 수 있기 때문이다. (이진수로 바꿨을 때, 1인 자리들만 덧셈)

따라서 아래와 같이 코드 작성이 가능하다.

 

소스코드)

int dp[10001];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M; cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int v, c, k; cin >> v >> c >> k;
        int t = 1;
        int temp;
        while (k > 0) {
            temp = min(k, t);
            for (int j = M; j >= v*temp; j--) {
                dp[j] = max(dp[j - v*temp] + c*temp, dp[j]);
            }
            t *= 2;
            k -= temp;
        }
    }
    int ans = 0;
    for (int i = 0; i <= M; i++) ans = max(dp[i], ans);
    cout << ans;
}

 

728x90
반응형

'알고리즘 문제풀이 > 백준 문제풀이' 카테고리의 다른 글

[BOJ 2437] 저울  (0) 2020.07.10
[BOJ 8980] 택배  (0) 2020.07.09
[BOJ 12920] 평범한 배낭 2  (3) 2020.07.07
[BOJ 2517] 달리기  (0) 2020.05.01
[BOJ 2568] 전깃줄 - 2  (0) 2020.04.22
[BOJ 11066] 파일 합치기  (0) 2019.07.22
  • 도와줘요 2022.05.20 13:11 댓글주소 수정/삭제 댓글쓰기

    궁금한 게 있습니다!
    혹시 문제를 풀 때 2와 같은 경우는
    비트로 쪼개면 어떻게 쪼개어 지나요?
    2^1 하나로 쪼개었더니
    1개를 담는 경우에 대해서 계산을 하지 못했습니다..

    • 코드를 확인해보시면, 2의 경우엔 1+1로 구현이 됩니다.
      처음엔 temp = min(k, t)에서 t = 1이므로 1개에 대해 계산을 하고, k -= temp에 의해 k는 1이 됩니다.
      그 다음 temp = min(k, t)에서 마찬가지로 temp = 1이 되기 때문에 결국 1+1로 계산합니다.

    • 모든 자연수 n는 1 + 2 + 4 + ... + 2^k + X 의 형태로 나타낼 수 있습니다. (k는 최대)

      1, 2, 4, ... , 2^k 의 조합을 통해 1부터 n - X까지 모든 값을 표현할 수 있고, 결과적으로 X는 반드시 1+2+4+...+2^k보다 작으므로 X에 {1, 2, 4, ..., 2^k}의 조합으로 만들어지는 1, 2, 3, ... 을 적절히 더해주면 1부터 n까지 모든 수를 표현할 수 있습니다.