[백준] 12920 평범한 배낭 2 with Python

📌 BOJ 12920 평범한 배낭 2

💡 조건

1. 민호는 BOJ 캠프에 가기 위해 가방을 싸려고 한다. 가방에 어떠한 물건들을 넣냐에 따라 민호의 만족도가 달라진다.

2. 집에 있는 모든 물건들을 넣으면 민호가 느낄 수 있는 만족도는 최대가 될 것이다.
   하지만 민호가 들 수 있는 가방의 무게는 정해져 있어 이를 초과해 물건을 넣을수가 없다.

3. 민호가 만족도를 최대로 느낄 수 있는 경우를 찾아보자.
   단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다.

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

5. 두 번째 줄부터 N개의 줄에 걸쳐 민호의 집에 있는 물건의 정보가 주어진다.
   각의 줄은 V, C, K (1 ≤ V ≤ M, 1 ≤ C, K ≤ 10,000, 1 ≤ V * K ≤ 10,000) 으로 이루어져 있다.
   V는 물건의 무게, C는 물건을 가방에 넣었을 때 올라가는 민호의 만족도, K는 물건의 개수이다.

6. 최대 무게를 넘기지 않게 물건을 담았을 때 민호가 느낄 수 있는 최대 만족도를 출력한다.

7. 냅색 알고리즘, 비트마스킹 유형의 문제

🖥 소스 코드

N, M = map(int, input().split())

dp = [0 for _ in range(M+1)]
weight, satisfaction = [], []
for _ in range(N):
    V, C, K = map(int, input().split())

    idx = 1
    while K > 0:
        tmp = min(idx, K)

        weight.append(V * tmp)
        satisfaction.append(C * tmp)

        idx *= 2
        K -= tmp

for i in range(len(weight)):
    for j in range(M, 0, -1):
        if j >= weight[i]:
            dp[j] = max(dp[j], dp[j-weight[i]] + satisfaction[i])

print(dp[M])

🔖 예제 및 실행결과

예제

2 3
2 7 1
1 9 3

실행결과

27

⌨️ 문제 풀이

1. 평범한 배낭 문제 시리즈이다.
   평범한 배낭 1 문제는 냅색, DP 문제이다.
   물품의 수 N, 버틸 수 있는 무게 K 라고 한다면 시간복잡도 O(NK)로 풀이할 수 있다.

2. 하지만 이 문제는 물건의 개수가 여러개이다. 즉, 물건이 중복으로 들어갈 수 있다는 것이다.
   물건이 중복으로 들어갈 수 있으며, V = 1, M = 10000, K = 10000 이라고 하면 while 반복문이 약 1억번 가까이 돌게 된다.
   이러면 무조건 TLE. 또한 일반 냅색에서는 2차원 배열을 이용했지만, 이 문제에서는 1차원 배열로 계산할 수 있다.

3. O(NM * logK)로 해결할 수 있는 알고리즘을 생각해봐야한다.
   다른 분들의 풀이를 확인하니, 비트마스킹 아이디어를 통해서 수를 표현하는 것을 알 수 있었다.
   이 아이디어의 핵심은 모든 수는 2의 제곱수들의 합으로 표현할 수 있다는 것이다.

4. 만약 같은 물건이 약 15개라고 한다면 이를 2의 제곱수들의 합으로 표현했을 때, 1 + 2 + 4 + 8 로 표현할 수 있다.
   그렇다면 DP 테이블에 1개, 2개, 4개, 8개 추가한 경우를 갱신시켜주면 된다.

5. DP 테이블을 M + 1 개 만들어주고, 무게와 만족도를 저장할 리스트를 생성한다.

6. 반복문을 N번 순회하면서 물건의 무게(V), 만족도(C), 물건의 개수(K)를 입력받는다.
   입력받은 물건을 한개 넣었을 경우부터 2 를 곱하면서 넣을 수 있는 개수를 계산하면서 만족도와 무게를 계산한다.
   계산한 각 값을 weight, satisfaction 리스트에 넣어준다. idx는 2를 곱해 2의 제곱수로 만들어준다.
   이미 계산한 2의 제곱수는 제외할 수 있도록 K에서 tmp를 빼준다.

7. 이후의 풀이는 냅색알고리즘과 같다.
   weight 리스트의 길이만큼 for 문을 순회(i)하고, 들 수 있는 최대 무게(M)부터 1까지 -1씩 내려가면서 순회(j)한다.

8. 이 때, j만큼 무게를 들 수 있을 때, weight 리스트의 i번째에 해당하는 물건을 넣을 수 있다면 dp[j]를 아래와 같이 갱신한다.

   dp[j] = max(dp[j], dp[j-weight[i]] + satisfaction[i])

9. dp[j] 째의 값과 (dp[현재 들 수 있는 최대무게 - i번째 물건의 무게] + i번째 물건의 만족도) 를 비교하여 갱신한다.

💾 배운점

1. 안그래도 어려운 냅색에서 비트마스크의 개념이 들어가니 매우 어려웠다.

2. 냅색도 냅색이지만, 모든 자연수가 2의 거듭제곱 수로 나타낼 수 있다는 아이디어는 생각치도 못했다.

3. (2)번의 아이디어를 기억하고 나중에 꼭 이러한 유형의 문제에서 적용할 수 있어야겠다.