ndb796
p.314 만들 수 없는 금액 문제에 대한 질문
제가 작성한 코드는 다음과 같이 모든 조합 가능한 경우의 수를 중복 없이 리스트에 넣은 후 그 리스트를 오름차순으로 정렬합니다. 그 뒤에 정렬 된 리스트를 순차적으로 탐색하여 인덱스 번호와 인덱스에 해당하는 값이 다르면 해당하는 값이 만들 수 없는 가장 작은 값인 것으로 판별하였습니다.
N = int(input()) coins = list(map(int, input().split())) results = [0] for i in range(len(coins)): for j in range(1, len(coins) + 1): val = sum(coins[i:j]) if val not in results: results.append(val) results.sort() for i in range(len(results)): if i != results[i]: print(i) break
시간복잡도가 O(n^2)인 알고리즘인데, 답안은 O(n) 복잡도의 알고리즘으로 제가 작성한 알고리즘 보다 성능이 좋았습니다.
다만 궁금한 점은 알고리즘 상 모든 조합 가능한 금액을 확인하는 것이 아닌데 중간에 확인 하지 않은 값들에 대해 만들 수 있는지는 어떻게 증명이 가 능한지요? 예를 들어 입력 예시로 주어진 5종류의 동전 3, 2, 1, 1, 9에 대해 확인하는 target의 값은 1, 2, 3, 5, 8 인데 4, 6, 7에 대해 만들 수 있는지 여부는 어떻게 증명할 수 있는건가요?
@camel-master 안녕하세요! 무려 1년이 지났지만 해당 해당 문제의 정답 코드를 보고 같은 궁금증이 생겨 comment 남깁니다. 저도 camel-master님과 유사하게 가능한 만들 수 있는 모든 조합의 금액을 구해 저장한 후에, 1부터 탐색하면서 빠진 값을 찾았습니다.
말씀하신 예시에서 정답 코드는 두 수의 조합으로 만든 수(예를 들면 5)는 확인하지 않는데요, 혹시 해결하셨나요?
제 풀이는 아래와 같습니다.
from itertools import combinations
# 입력 받기
N = int(input())
coins = list(map(int, input().split()))
# 가진 동전으로 만들 수 있는 모든 금액 구하기
combis = []
for i in range(1, N+1):
combis += map(sum, list(combinations(coins, i)))
combis = set(combis) # 중복 제거
total = {i for i in range(1, max(combis)+1)} # 1원 ~ 만들 수 있는 최고 금액까지 집합으로 만들어 저장
print(min(total - combis)) # 차집합 중 최소값 구하기