문제 소개
동전의 가치를 담은 리스트 coins와 같은 길이의 수량 리스트 quantities가 주어져 있다고 가정해 보겠습니다. i번째 동전의 가치는 coins[i]이며, 현재 i번째 동전을 quantities[i]개만큼 가지고 있습니다.
이때, 가지고 있는 동전들 중 비어 있지 않은 그룹을 선택하여 만들 수 있는 서로 다른 합계 값의 개수를 구하는 것이 이 문제의 목표입니다.
예시
입력이 coins = [1, 2, 5], quantities = [1, 2, 1]이라면 출력은 10이 됩니다. 만들 수 있는 고유한 합계는 다음과 같습니다.
- [1] = 1
- [2] = 2
- [1, 2] = 3
- [2, 2] = 4
- [5] = 5
- [1, 5] = 6
- [2, 5] = 7
- [1, 2, 5] = 8
- [2, 2, 5] = 9
- [1, 2, 2, 5] = 10
즉, 총 10가지의 서로 다른 합계를 만들 수 있습니다.
풀이 접근 방법
이 문제는 재귀 함수를 사용하여 해결할 수 있습니다. 각 동전 종류에 대해 0개부터 최대 보유 수량까지 선택하는 모든 경우를 탐색하면서, 지금까지의 합계를 집합(set)에 저장하면 중복 없이 고유한 합계 값을 수집할 수 있습니다.
알고리즘 단계
- 재귀 함수
rec(i, res)를 정의합니다. 여기서i는 현재 탐색 중인 동전의 인덱스,res는 지금까지 누적된 합계입니다. i가 동전 리스트의 길이와 같으면 함수를 종료합니다.- k를 0부터
quantities[i]까지 반복하면서cur = res + k * coins[i]를 계산하고, 이 값을 결과 집합fres에 추가한 뒤rec(i + 1, cur)을 호출합니다. - 메인 부분에서 빈 집합
fres를 생성하고rec(0, 0)을 호출합니다. - 마지막으로
fres의 크기에서 1을 뺀 값을 반환합니다. (모든 동전을 선택하지 않은 경우인 0이 집합에 포함되므로 이를 제외하기 위함입니다.)
구현 예제 코드
class Solution:
def solve(self, coins, quantities):
def rec(i, res):
if i == len(coins):
return
for k in range(0, quantities[i] + 1):
cur = res + k * coins[i]
fres.add(cur)
rec(i + 1, cur)
fres = set()
rec(0, 0)
return len(fres) - 1
ob = Solution()
coins = [1, 2, 5]
quantities = [1, 2, 1]
print(ob.solve(coins, quantities))
입력
[1, 2, 5], [1, 2, 1]
출력
10
코드 설명 및 참고 사항
위 코드에서 반환값에서 1을 빼는 이유는 재귀 탐색 과정에서 어떤 동전도 선택하지 않은 상태의 합계인 0이 자동으로 집합에 포함되기 때문입니다. 문제에서 요구하는 것은 '비어 있지 않은 그룹'의 합계이므로, 0을 제외하기 위해 len(fres) - 1을 반환합니다.
집합(set)을 사용하면 동일한 합계가 여러 번 계산되더라도 자동으로 중복이 제거되므로, 별도의 중복 검사 없이 간결하게 고유한 합계의 개수를 구할 수 있습니다. 다만 이 방식은 가능한 모든 조합을 탐색하므로, 동전 수량이 매우 많아지면 시간 복잡도가 증가할 수 있다는 점을 유의해야 합니다.