1049. 마지막 돌의 무게 II

이 문제는 돌들을 두 그룹으로 나누어 각각 충돌했을 때 남는 돌의 무게를 최소화하는 것이 목적이다. 이는 0-1 배낭 문제로 변환할 수 있다.

각 돌의 무게와 가치는 동일하게 설정하며, 총 무게의 절반을 목표로 하는 배낭 용량을 정한다.

일차원 배열 버전

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int totalWeight = Arrays.stream(stones).sum();
        int target = totalWeight / 2;
        int[] dp = new int[target + 1];
        
        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }
        
        return totalWeight - 2 * dp[target];
    }
}

• 시간 복잡도: O(n × m), n은 돌 개수, m은 총 무게의 절반
• 공간 복잡도: O(m)

이차원 배열 버전

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int totalWeight = 0;
        for (int stone : stones) totalWeight += stone;
        int target = totalWeight / 2;
        
        int[][] dp = new int[stones.length][target + 1];
        
        // 초기화: 첫 번째 돌에 대해 가능한 경우
        for (int j = stones[0]; j <= target; j++) {
            dp[0][j] = stones[0];
        }
        
        for (int i = 1; i < stones.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (j >= stones[i]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - stones[i]] + stones[i]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        return totalWeight - 2 * dp[stones.length - 1][target];
    }
}

494. 목표 합계

배열 내 요소에 + 또는 - 부호를 붙여 전체 합이 특정 값이 되도록 만드는 방법의 수를 구하는 문제다. 이를 0-1 배낭 문제로 해석하면, 양수 부분의 합을 정해두고 해당 배낭을 채우는 방법의 수를 계산하면 된다.

결과적으로, left = (sum + target) / 2 를 구하고, 이 값을 배낭 용량으로 삼아 가능한 조합 수를 세면 된다.

이차원 배열 버전

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (Math.abs(target) > sum || (sum + target) % 2 == 1) return 0;
        
        int bagSize = (sum + target) / 2;
        int[][] dp = new int[nums.length][bagSize + 1];
        
        // 초기화: 0번 인덱스 처리
        if (nums[0] <= bagSize) dp[0][nums[0]] = 1;
        
        int zeroCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) zeroCount++;
            dp[i][0] = (int) Math.pow(2, zeroCount);
        }
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (nums[i] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i]];
                }
            }
        }
        
        return dp[nums.length - 1][bagSize];
    }
}

일차원 배열 버전

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (Math.abs(target) > sum || (sum + target) % 2 == 1) return 0;
        
        int bagSize = (sum + target) / 2;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;
        
        for (int num : nums) {
            for (int j = bagSize; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        
        return dp[bagSize];
    }
}

• 시간 복잡도: O(n × m), n은 요소 수, m은 배낭 용량
• 공간 복잡도: O(m)

474. 0과 1의 개수

문자열 배열에서 각 문자열의 0과 1 개수를 고려하여, 총 0개수가 ≤ m, 1개수가 ≤ n인 최대 서브셋 크기를 찾는 문제다.

이는 두 가지 제약 조건이 있는 0-1 배낭 문제로 간주할 수 있으며, 각 문자열은 물체, 0과 1의 개수는 무게로 취급된다.

이차원 배열 해결법

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        
        for (String str : strs) {
            int zeros = 0, ones = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        
        return dp[m][n];
    }
}

• 시간 복잡도: O(k × m × n), k는 문자열 개수
• 공간 복잡도: O(m × n)