서로 다른 숫자로 이루어진 리스트 nums와 하나의 숫자 k가 주어졌을 때, 원소들의 합이 정확히 k가 되는 고유한 조합의 개수를 구하는 문제입니다. 조합을 만들 때는 같은 숫자를 여러 번 재사용할 수 있습니다.
예를 들어 입력이 nums = [2, 4, 5], k = 4라고 한다면 출력은 2가 됩니다. [2, 2]와 [4], 이렇게 두 가지 조합으로 합이 4를 만들 수 있기 때문입니다.
동적 계획법(DP)을 이용한 풀이
이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.
- 크기가 k+1인 리스트 table을 만들고 모든 요소를 0으로 초기화합니다.
- table[0]을 1로 설정합니다. (합이 0이 되는 경우는 아무것도 선택하지 않는 한 가지 방법뿐이므로)
- nums에 있는 각 숫자 num에 대해 다음을 반복합니다.
- i가 num부터 k까지일 때, table[i] = table[i] + table[i - num]을 수행합니다.
- 마지막으로 table[k]를 반환합니다.
여기서 중요한 포인트는 숫자를 순회하는 바깥 루프가 먼저 오고, 목표 합을 순회하는 안쪽 루프가 나중에 온다는 것입니다. 이런 순서 덕분에 같은 숫자를 여러 번 사용하는 '조합(combination)'만 세어지고, 원소의 순서만 다른 중복된 '순열(permutation)'은 자연스럽게 제외됩니다.
예제 코드
class Solution:
def solve(self, nums, k):
table = [1] + [0] * k
for num in nums:
for i in range(num, k + 1):
table[i] += table[i - num]
return table[k]
ob = Solution()
nums = [2, 4, 5]
k = 4
print(ob.solve(nums, k))
입력
[2, 4, 5], 4
출력
2
복잡도 분석
시간 복잡도는 O(len(nums) × k)이며, 공간 복잡도는 O(k)입니다. 즉, 입력 리스트의 크기와 목표 값 k에 비례하여 선형적으로 계산량이 늘어나므로 상당히 효율적인 알고리즘입니다.