Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 마지막 돌의 무게 II — 배낭 DP 접근법

문제 설명

양의 정수 가중치를 가진 돌들이 여러 개 주어져 있습니다. 매 턴마다 임의의 두 돌을 골라 서로 부딪히게 하는데, 두 돌의 무게를 각각 x, y(x ≤ y)라고 할 때 충돌 결과는 다음과 같습니다.

  • x = y인 경우: 두 돌은 모두 완전히 파괴됩니다.

  • x ≠ y인 경우: 무게 x인 돌은 완전히 파괴되고, 무게 y인 돌은 새로운 무게 y − x를 갖습니다.

이 과정을 반복하면 최종적으로 최대 1개의 돌만 남게 되는데, 이때 남은 돌의 최소 가능한 무게를 구하는 것이 목표입니다. 모든 돌이 파괴된다면 답은 0입니다.

예시

입력이 [2,7,4,1,8,1]일 때 출력은 1입니다. 과정을 하나씩 살펴보면 다음과 같습니다.

  • (2, 4)를 부딪힘 → [2, 7, 1, 8, 1]
  • (7, 8)을 부딪힘 → [2, 1, 1, 1]
  • (2, 1)을 부딪힘 → [1, 1, 1]
  • (1, 1)을 부딪힘 → [1]

마지막에 남은 돌의 무게는 1입니다.

접근 방법 — 부분집합 합으로 치환하기

이 문제는 단순 시뮬레이션처럼 보이지만, 관점을 바꾸면 분할(partition) 문제로 볼 수 있습니다. 충돌 연산은 결국 각 돌에 '+' 또는 '−' 부호를 붙이는 것과 같아서, 최종 결과는 "두 그룹의 합의 차이"가 됩니다.

전체 돌 무게의 합을 total, 한쪽 그룹의 합을 reach라고 하면 답은 total − 2 × reach입니다. 따라서 reach가 total / 2에 최대한 가깝도록 만들 수 있는 부분집합을 찾으면 되며, 이는 전형적인 0/1 배낭(Knapsack) 동적 계획법으로 해결할 수 있습니다.

알고리즘 단계

  1. n := 돌 배열의 크기, total := 0으로 초기화
  2. i를 0부터 n−1까지 순회하며 total := total + stones[i]
  3. req := total / 2
  4. 크기가 req + 1인 불리언 배열 dp를 만들고 false로 채움
  5. dp[0] := true, reach := 0으로 설정
  6. i를 0부터 n−1까지 순회하며, 각 i에 대해 j를 req부터 시작해 j − stones[i] ≥ 0인 동안 1씩 감소시키면서:
    • dp[j] := dp[j] 또는 dp[j − stones[i]] (둘 중 하나라도 true면 true)
    • dp[j]가 true이면 reach := max(reach, j)
  7. total − (2 × reach)를 반환

내부 루프에서 j를 내림차순으로 순회하는 이유는 같은 돌을 두 번 사용하는 것을 방지하기 위해서입니다. 이는 0/1 배낭 문제의 표준적인 기법입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int total = 0;
        for(int i = 0; i < n; i++){
            total += stones[i];
        }
        int req = total / 2;
        vector <bool> dp(req + 1, false);
        dp[0] = true;
        int reach = 0;
        for(int i = 0; i < n; i++){
            for(int j = req; j - stones[i] >= 0; j--){
                dp[j] = dp[j] || dp[j - stones[i]];
                if(dp[j]) reach = max(reach, j);
            }
        }
        return total - (2 * reach);
    }
};
main(){
    vector<int> v = {2,7,4,1,8,1};
    Solution ob;
    cout << (ob.lastStoneWeightII(v));
}

입력

[2,7,4,1,8,1]

출력

1

복잡도 분석

시간 복잡도는 O(n × total / 2)이며, 공간 복잡도는 O(total / 2)입니다. 여기서 n은 돌의 개수입니다. 부분집합 합 테이블을 1차원 배열로 압축했기 때문에 메모리 사용량도 효율적입니다.