문제 설명
양수로만 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 이제 다음과 같은 연산을 수행할 수 있습니다. 리스트에서 두 값 a와 b(a ≤ b)를 제거한 뒤, 만약 a < b라면 그 차이인 b-a를 다시 리스트에 삽입하는 것입니다. 이 연산은 원하는 만큼 몇 번이든 반복할 수 있으며, 우리의 목표는 마지막에 남길 수 있는 가장 작은 숫자를 구하는 것입니다. 만약 리스트가 완전히 비게 된다면 0을 반환하면 됩니다.
예를 들어 입력이 nums = [2, 4, 5]라고 한다면 출력은 1이 됩니다. 먼저 4와 5를 선택해 그 차이인 1을 리스트에 다시 넣으면 [2, 1]이 되고, 이어서 2와 1을 선택하면 [1]만 남기 때문입니다.
해결 접근 방법
이 문제의 핵심은 각 숫자에 대해 두 가지 선택지를 모두 고려하는 것입니다. 어떤 숫자를 다른 숫자와 짝지어 차감 연산에 사용하면 전체 합에서 그 숫자의 두 배만큼 줄어드는 효과가 있고, 사용하지 않으면 합이 그대로 유지됩니다. 따라서 재귀적으로 모든 경우를 탐색하며 가능한 최소 값을 찾을 수 있습니다.
문제를 해결하기 위해 다음 단계를 따릅니다 −
- s := nums에 있는 모든 요소의 합
- 함수 f()를 정의합니다. 이 함수는 인덱스 i와 현재 합 s를 인자로 받습니다.
- 만약 i >= nums의 크기라면
- s를 반환합니다.
- n := nums[i]
- 만약 s - 2 * n < 0이라면
- f(i + 1, s)를 반환합니다.
- f(i + 1, s - 2 * n)과 f(i + 1, s) 중 더 작은 값을 반환합니다.
- 메인 메서드에서는 f(0, s)를 반환합니다.
즉, 각 숫자를 "차감 연산에 사용할지 말지" 결정하면서 모든 조합을 탐색하는 방식입니다. 이는 부분 집합의 합이 전체 합의 절반에 최대한 가깝도록 분할하는 문제와 본질적으로 같은 구조입니다.
예시 코드
더 나은 이해를 돕기 위해 다음 구현을 살펴보겠습니다 −
def solve(nums):
s = sum(nums)
def f(i, s):
if i >= len(nums):
return s
n = nums[i]
if s - 2 * n < 0:
return f(i + 1, s)
return min(f(i + 1, s - 2 * n), f(i + 1, s))
return f(0, s)
nums = [2, 4, 5]
print(solve(nums))입력
[2, 4, 5]
출력
1
복잡도 분석
이 풀이는 각 숫자마다 두 가지 선택지를 가지므로 시간 복잡도는 O(2^n)입니다. 리스트의 크기가 커진다면 메모이제이션(memoization)을 활용해 동일한 (i, s) 상태의 결과를 캐싱하면 중복 계산을 크게 줄일 수 있습니다.