LeetCode 1049: 돌 무게 최소화하기

문제는 일련의 돌들이 주어졌을 때, 두 그룹으로 나누어 서로를 부딪히게 하며 마지막 남은 돌의 최소 무게를 구하는 것이다. 이는 결국 전체 무게 합 sum에 대해 가능한 한 균등하게 두 집합으로 분할하는 문제로 전환된다. 즉, 한쪽 그룹의 무게 합이 sum / 2에 가까워야 하며, 이는 01 배낭 문제와 동일한 구조를 가진다.

해결 전략:
각 돌은 무게이자 가치로 간주되며, 배낭의 용량은 sum / 2로 설정한다. DP 배열 dp[j]는 용량 j의 배낭에 담을 수 있는 최대 무게를 의미한다. 점진적으로 돌들을 탐색하면서 역순으로 배낭을 갱신한다.

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = accumulate(stones.begin(), stones.end(), 0);
        int capacity = total / 2;
        vector<int> dp(capacity + 1, 0);

        for (int stone : stones) {
            for (int j = capacity; j >= stone; j--) {
                dp[j] = max(dp[j], dp[j - stone] + stone);
            }
        }

        return total - 2 * dp[capacity];
    }
};

최종 결과는 전체 - 2 × 최대_부분합으로 계산되며, 이는 두 그룹 간 무게 차이를 의미한다.

LeetCode 494: 목표 합계 경우의 수

배열 원소에 + 또는 - 기호를 붙여서 특정 목표값 target을 만들 수 있는 방법의 수를 구해야 한다. 이 역시 부분집합 분할 문제로 해석 가능하다. 양수 그룹의 합을 left, 음수 그룹의 합을 right라 하면 다음 관계가 성립한다:

• left + right = sum
• left - right = target
• → left = (sum + target) / 2

즉, 합이 정확히 (sum + target)/2이 되는 부분집합의 개수를 세면 된다. 이는 "배낭을 정확히 채우는 방법의 수"를 구하는 전형적인 DP 문제이다.

DP 정의:
dp[j]: 합이 j가 되도록 숫자를 선택하는 방법의 수.
점화식: dp[j] += dp[j - num]
초기값: dp[0] = 1 (빈 집합으로 0을 만들 수 있음)

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        
        if (abs(target) > sum || (sum + target) % 2 != 0) return 0;
        
        int left = (sum + target) / 2;
        vector<int> dp(left + 1, 0);
        dp[0] = 1;

        for (int num : nums) {
            for (int j = left; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[left];
    }
};

주의: left가 음수가 되거나 홀수인 경우 유효하지 않으므로 사전에 필터링해야 한다.

LeetCode 474: 제한된 0과 1로 만들 수 있는 문자열 개수

주어진 문자열 배열에서 각 문자열은 0과 1을 포함하며, 최대 m개의 '0'과 n개의 '1'을 사용하여 만들 수 있는 문자열의 최대 개수를 구하는 문제이다. 이는 2차원 배낭 문제로 볼 수 있다.

DP 상태 정의:
dp[i][j]: i개의 0과 j개의 1을 사용해 구성할 수 있는 문자열의 최대 개수.
각 문자열은 고유한 "비용" (zero_count, one_count)을 가지며, 가치는 1로 간주된다.

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (const string& s : strs) {
            int zeros = count(s.begin(), s.end(), '0');
            int ones = s.length() - zeros;

            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

내부 반복문은 2차원에서 역순으로 진행되어 중복 사용을 방지한다.