01 배낭 문제 기반의 최적화 및 조합 알고리즘 응용
LeetCode 1049: 돌 무게 최소화하기
문제는 일련의 돌들이 주어졌을 때, 두 그룹으로 나누어 서로를 부딪히게 하며 마지막 남은 돌의 최소 무게를 구하는 것이다. 이는 결국 전체 무게 합 sum에 대해 가능한 한 균등하게 두 집합으로 분할하는 문제로 전환된다. 즉, 한쪽 그룹의 무게 합이 sum / 2에 가까워야 하며, 이는 01 배낭 문제와 동일한 구조를 가진다.
해결 전략 ...
7월 19일 04:27에 게시됨