[DP: 0 / 1 Knapsack] 1049. Last Stone Weight II ★★★★★★★

LeetCode/NeetCode

[DP: 0 / 1 Knapsack] 1049. Last Stone Weight II ★★★★★★★

hyunkookim 2025. 4. 13. 08:11

📌 문제 요약

stones[i]: 각 돌의 무게
두 개를 선택해 부딪히면,
- 같으면 둘 다 없어짐
- 다르면 무게가 |x - y|인 돌이 하나 남음
이 과정을 반복 → 마지막에 남는 돌의 최소 무게를 반환하라는 문제

✅ 잘못된 풀이

실제 문제에서 설명된 smash 동작을 직접 시뮬레이션하려고 한 코드야.
그런데 이 방식이 **틀린 이유는 "최적의 순서를 보장할 수 없기 때문"**이야.

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 2개 골라서 두개가 같으면, 배열에서 제거
        # 2개 골라서, 두개가 다르면, 두개 제거하고, 그 차이(큰거-작은거) 를 추가
        # 하나 남으면, 그값을 return

        while len(stones) > 1:
            stones.sort()
            s1 = stones.pop()
            s2 = stones.pop()
            if s1 == s2:
                continue
            else:
                stones.append(abs(s2-s1))
        # print(stones)
        return 0 if not stones else stones[0]

최대 heap 사용

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 2개 골라서 두개가 같으면, 배열에서 제거
        # 2개 골라서, 두개가 다르면, 두개 제거하고, 그 차이(큰거-작은거) 를 추가
        # 하나 남으면, 그값을 return
        
        # heap은 기본이 min heap이므로, 음수로 바꿔서 최대 힙처럼 사용
        max_heap = [-s for s in stones]
        heapq.heapify(max_heap)

        while len(max_heap) > 1:
            # 가장 무거운 두 개 꺼내기
            s1 = -heapq.heappop(max_heap)
            s2 = -heapq.heappop(max_heap)

            # 두 돌이 다르면 → 차이를 다시 넣기
            if s1 != s2:
                heapq.heappush(max_heap, -(s1 - s2))

        # 남은 돌이 없으면 0, 있으면 양수로 다시 변환해서 반환
        return -max_heap[0] if max_heap else 0

이건 얼핏 보면 말이 되는데, 항상 "현재 가장 큰 두 개"만 골라서 처리해.
하지만, 이 게임은 단순히 그리디(greedy)하게 가장 큰 두 개를 고른다고 해서
최적 결과가 나온다는 보장이 없어.

✅ 그래서 정답 풀이 방식은?

이건 결국 모든 가능한 나누기 조합 중
두 그룹의 무게 차이가 최소가 되도록 하는 문제야.

➡ 그래서 부분집합 합이나 Knapsack을 써야 정답을 보장할 수 있어.

🧠 핵심 아이디어: 두 그룹으로 나누기

결국 모든 smash는 "두 그룹의 무게 차"만 남기게 돼
즉, 돌들을 두 그룹으로 나눴을 때:

🔻 abs(sum(group1) - sum(group2)) 이 최소가 되도록 나누는 문제야!

👉 이건 0-1 Knapsack (부분집합 합 문제) 과 똑같음!

✔️ 목표

전체 합 S = sum(stones)
subset_sum을 S // 2 이하로 만들면서
→ 가능한 가장 큰 subset_sum을 찾자
그러면 나머지 그룹은 S - subset_sum

최종적으로:

최소 차이 = abs(S - 2 * subset_sum)

🧠 이 문제는 결국 이런 문제야:

돌들을 두 그룹으로 나누라.
두 그룹의 무게 차이를 최소화하라.

🎯 목표:

전체 돌 무게 합 S = sum(stones)
돌들을 두 그룹으로 나누자:
- 그룹 A: sumA
- 그룹 B: sumB

🔄 그럼 smash 결과는?

smash 후 남는 값 = |sumA - sumB|
왜냐면, smash는 결과적으로 두 그룹의 차이만 남게 되는 과정이야.

✅ 그럼 왜 S - 2 * subset_sum?

우리는 지금:

sumA + sumB = S (전체 돌의 합)
sumA 또는 sumB 중 하나만 subset_sum으로 선택했어.

그럼 나머지 그룹은 S - subset_sum이겠지?

→ 두 그룹 차이 = abs((S - subset_sum) - subset_sum)
= abs(S - 2 * subset_sum)

📌 예제로 볼까?

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

S = 23

S // 2 = 11 → 최대한 11에 가까운 subset sum을 만들자
예를 들어 subset_sum = 11 을 만들었다고 해보자
나머지 그룹은 23 - 11 = 12
두 그룹 차이 = |12 - 11| = 1

→ 최소 차이는 abs(23 - 2 * 11) = 1
→ ✅ 이게 바로 S - 2 * subset_sum 공식이야!

🔄 반대로 하면?

S = 23, subset_sum = 10
→ 나머지 그룹: 13 차이
= abs(13 - 10) = 3 = abs(S - 2 * 10)

✅ 정리

의미	수식
전체 무게 합	S = sum(stones)
두 그룹 무게 차이	abs(sumA - sumB)
sumA = subset_sum 이라고 했을 때	sumB = S - subset_sum
차이 =	abs((S - subset_sum) - subset_sum) → abs(S - 2 * subset_sum)

from collections import defaultdict

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 모든 돌의 무게를 합산한 값 (전체 무게 합)
        total = sum(stones)

        # 돌들을 두 그룹으로 나누었을 때, 가능한 가장 균형 잡힌 절반 무게를 목표로 설정
        target = total // 2  # 부분집합 중 절반 이하에서 가장 큰 합을 구하는 것이 목표

        # dp[i] = 무게 합이 i일 때 만들 수 있는 최대 부분집합의 합
        # 기본값 0으로 초기화되며, 딕셔너리처럼 자유롭게 접근 가능
        dp = defaultdict(int)

        # 각 돌을 하나씩 순회하면서 dp 테이블을 갱신
        for stone in stones:
            # 현재 상태의 dp를 복사해 저장
            # 이 복사본은 현재 돌을 선택하기 이전의 상태를 의미
            prev_dp = dp.copy()

            # 무게 합을 target부터 거꾸로 내려오면서 갱신 (중복 선택 방지를 위해 역순 순회)
            for i in range(target, stone - 1, -1):
                # 현재 무게 i를 만들 때:
                # 1. 이전 값 유지 (dp[i])
                # 2. 이 stone을 사용해서 i - stone 무게에 이 stone을 더한 값 (prev_dp[i - stone] + stone)
                # 둘 중 더 큰 값을 선택하여 dp[i]에 저장
                dp[i] = max(dp[i], prev_dp[i - stone] + stone)

        # 전체 무게 total에서 부분집합 합 dp[target]을 두 배 빼면 두 그룹 차이가 됨
        # 전체 - 2 * 가장 가까운 절반 = 두 그룹 차이 최소값
        return total - 2 * dp[target]

🔍 왜 prev_dp = dp.copy() 가 필요해?

defaultdict는 리스트와 다르게 참조가 유지돼서,
dp[i - stone]을 읽고, 바로 dp[i]에 쓸 때 동일한 딕셔너리에서 읽고 쓰는 문제가 생겨
→ 그래서 copy()로 읽기 전용 원본을 만들어두는 거야

https://youtu.be/gdXkkmzvR3c

✅ Top-down DFS + 메모이제이션 방식,
문제 핵심인 두 그룹으로 나누기를 재귀적으로 탐색해서 최소 차이를 구하는 방식

from math import ceil

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 모든 돌 무게의 총합
        stoneSum = sum(stones)

        # 목표는 총합을 절반(또는 그 이상)에 가깝게 만드는 부분집합을 찾는 것
        # total은 누적합이니까, ceil을 써야 23/2 같은 경우 12로 맞춰짐
        target = ceil(stoneSum / 2)

        # 메모이제이션을 위한 딕셔너리: (인덱스, 현재까지의 합)을 key로 저장
        dp = {}

        # dfs(i, total): stones[i:] 범위 내에서
        # 현재까지 고른 무게 합이 total일 때,
        # 전체 합 stoneSum을 두 그룹으로 나눴을 때의 최소 차이를 반환
        def dfs(i, total):
            # ✅ 종료 조건 1: total이 절반 이상인 경우 더 탐색할 필요 없음
            # ✅ 종료 조건 2: 모든 돌을 다 봤을 경우
            if total >= target or i == len(stones):
                # 두 그룹의 차이 = |total - (stoneSum - total)| = |2*total - stoneSum|
                # total: 현재 그룹의 무게 합
                # stoneSum - total: 나머지 그룹의 무게 합
                # 두 그룹 무게 차이의 절댓값 반환
                return abs(total - (stoneSum - total))
            
            # 메모이제이션: 이미 계산된 (i, total)에 대해 저장된 결과가 있다면 바로 반환
            if (i, total) in dp:
                return dp[(i, total)] 

            # 이 돌을 선택하지 않는 경우 vs 선택하는 경우 중 최소 차이를 선택
            # 1. 현재 돌을 포함하지 않음 → dfs(i+1, total)
            # 2. 현재 돌을 포함함 → dfs(i+1, total + stones[i])
            dp[(i, total)] = min(
                dfs(i + 1, total),
                dfs(i + 1, total + stones[i])
            )

            return dp[(i, total)]

        # 초기 상태: 인덱스 0번, 현재까지 합 0
        return dfs(0, 0)

🔍 특히 궁금해한 부분 다시 설명

if total >= target or i == len(stones):
    return abs(total - (stoneSum - total))

이 부분은 재귀 종료 조건인데, 이렇게 생각하면 돼:

돌을 다 골랐거나 (i == len(stones)),
이미 목표 절반을 넘겼다면 (total >= target)
→ 더 고를 필요 없이 현재 상태에서 두 그룹 차이 계산해서 반환

그룹 A = total
그룹 B = stoneSum - total
차이 = abs(A - B) = abs(2*total - stoneSum)

이 차이를 최소화하는 total 값을 찾는 게 목표야!

🔍 dp[(i, total)] 가 뭘 의미?

✅ 정의

dp[(i, total)]은
현재 stones[i:] 구간에서
지금까지 선택한 돌들의 무게 합이 total일 때,
최종적으로 두 그룹으로 나눴을 때 생기는 무게 차이의 최솟값을 의미해.

🧠 직관적으로 다시 말하면:

지금까지 total이라는 무게를 모았어 (선택한 돌들의 무게 합).
이제 남은 돌들(stones[i:]) 중에서 뭘 더 선택할지 고민 중이야.
이 상태에서 최적의 선택을 했을 때 두 그룹의 차이가 최소가 되도록 하고 싶어.

그래서 dp[(i, total)]는 결국 다음과 같은 질문의 답이야:

"돌 i번부터 끝까지 살펴보면서, 지금까지의 무게 합이 total일 때,
두 그룹으로 나눴을 때 생기는 최소 차이는 얼마인가요?"

🧪 예시로 보면 더 쉬워!

stones = [2, 4, 7]

stoneSum = 13

target = ceil(13 / 2) = 7

우리가 dfs(1, 2)을 호출했다고 하면:

i = 1 → 현재 1번 돌(4)부터 살펴볼 차례
total = 2 → 앞에서 2라는 무게를 이미 선택함

그러면 dp[(1, 2)]는 이런 의미야:

"돌 [4, 7]을 가지고, 지금까지 선택한 무게가 2일 때,
두 그룹의 무게 차이를 최소로 만들면 그 차이는 얼마인가요?"

💡 핵심 요약

표현	의미
i	지금 돌을 고르고 있는 위치 인덱스
total	지금까지 고른 돌들의 무게 합
dp[(i, total)]	stones[i:] 범위 내에서 total을 기반으로 최적의 선택을 했을 때, 두 그룹 차이의 최소값

'LeetCode > NeetCode' 카테고리의 다른 글

567. Permutation in String (0)	2025.04.16
[DP: Unbounded Knapsack] 322. Coin Change (2)	2025.04.13
[DP: 0 / 1 Knapsack] 474. Ones and Zeroes ★★★★★ (0)	2025.04.13
[DP: 0 / 1 Knapsack] 416. Partition Equal Subset Sum ★★★ (0)	2025.04.12
[위상 정렬] 269. Alien Dictionary ★★★★★ (0)	2025.04.12

현재글[DP: 0 / 1 Knapsack] 1049. Last Stone Weight II ★★★★★★★

hyunkookim 님의 블로그

hyunkookim 님의 블로그 입니다.

슬라이딩윈도우, LeetCode, Coding Test, 누적합, BFS, BST, dfs, 티스토리챌린지, dp, heap, Backtracking, leetcode75, top150, 우선순위큐, Two pointers, neetcode150, tree, neetcode, 오블완, array / string,

Today :
Yesterday :

hyunkookim 님의 블로그