문제 개요
배열 nums와 목표값 sum이 주어졌다고 가정해 봅시다. 우리가 확인해야 할 것은 nums에 있는 요소들을 더하여 sum을 만들 수 있는지 여부입니다. 이때 하나의 요소를 여러 번 반복해서 사용할 수 있다는 점이 핵심입니다.
예를 들어, 입력이 nums = [2, 3, 5], sum = 28이라면 출력은 True가 됩니다. 5 + 5 + 5 + 5 + 3 + 3 + 2처럼 요소를 조합하면 정확히 28을 만들 수 있기 때문입니다.
이 문제는 동전 교환(Coin Change) 문제와 유사한 전형적인 동적 계획법(Dynamic Programming) 문제로, 도달 가능한 모든 합계를 기록하는 테이블을 활용하여 해결할 수 있습니다.
풀이 접근 방식
다음 단계를 따라 문제를 해결합니다.
MAX:= 1000으로 설정합니다.table:= 크기가 MAX인 배열을 생성하고 0으로 초기화합니다. 각 인덱스는 해당 합계를 만들 수 있는지 여부를 나타냅니다.- 함수
util()을 정의합니다. 이 함수는 nums를 인자로 받습니다. table[0]:= 1로 설정합니다. (아무것도 선택하지 않으면 합계가 0이 되므로)- 리스트 nums를 오름차순으로 정렬합니다.
- i를 0부터 len(nums) - 1까지 반복합니다.
- val := nums[i]
- 만약
table[val]이 이미 0이 아니라면, 다음 반복으로 건너뜁니다. (중복 연산 방지) - j를 0부터 MAX - val - 1까지 반복합니다.
- 만약
table[j]가 0이 아니라면,table[j + val]:= 1로 설정합니다.
- 만약
- 메인 로직에서는 다음을 수행합니다.
util(nums)를 호출합니다.table[sum]이 0이 아니라면 True를 반환합니다.- 그렇지 않으면 False를 반환합니다.
구현 예제
아래 코드를 통해 실제 구현 방법을 살펴보겠습니다.
MAX = 1000
table = [0] * MAX
def util(nums):
table[0] = 1
nums.sort()
for i in range(len(nums)):
val = nums[i]
if table[val]:
continue
for j in range(MAX - val):
if table[j]:
table[j + val] = 1
def solve(nums, sum):
util(nums)
if table[sum]:
return True
return False
nums = [2, 3, 5]
sum = 28
print(solve(nums, sum))
입력
[2, 3, 5], 28
출력
True
동작 원리 설명
이 알고리즘의 핵심은 table 배열입니다. table[i]의 값이 1이면, 배열의 요소들을 조합하여 합계 i를 만들 수 있다는 의미입니다. 먼저 table[0]을 1로 초기화한 후, 각 숫자 val에 대해 현재 도달 가능한 모든 합계 j에 val을 더한 새로운 합계(j + val)를 도달 가능한 상태로 표시합니다.
이미 table[val]이 설정되어 있는 경우 반복을 건너뛰는 최적화 덕분에 같은 숫자를 여러 번 처리하는 낭비를 줄일 수 있습니다. 마지막으로 table[sum]을 확인하여 목표 합계를 만들 수 있는지 판단합니다.
이 알고리즘의 시간 복잡도는 O(n × MAX), 공간 복잡도는 O(MAX)입니다. 참고로, 파이썬에서 sum은 내장 함수 이름이므로 실무에서는 변수명 충돌을 피하기 위해 target 같은 다른 이름을 사용하는 것이 좋습니다.