[algorithm][Quiz] 만들 수 없는 금액
문제
주어진 N개의 동전으로 만들 수 있는 값 중 최소를 구하는 문제.
출처 - [이것이 코딩 테스트다] 교재 Q4
풀이과정
각각의 합으로 만들 수 있는 금액 중 최소를 구하는 데에 효율적인 구현이 생각나지 않았다.
(1개~N개 동전을 모두 쓸 수 있는 점이 헷갈림)
모든 합계의 경우를 구하고 해당하지 않는 최소를 구할까 싶었지만 바람직하지 않음
정답
- 책에 기술된 내용
화폐를 기준으로 오름차순 정렬한다. 이후 1부터 차례로 특정한 금액을 만들 수 있는지를 확인한다.
1부터 target-1까지의 모든 금액을 만들 수 있다고 가정해보자. 우리는 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있다면, target 값을 업데이트한다.
n = int(input())
data = list(map(int, input().split()))
data.sort()
target = 1
for x in data:
if target < x:
break
target += x
print(target)
- 내 생각
처음에 풀이와 해설을 보고도 이해가 잘 가지 않았다.
이건 직접 경우를 따지다보면 감이 잡히는데 처음 비교값인 target 1부터 차례로 합해지는 값, 즉 target -1 까지는 그 단계별로 확인된 값들로 인해 만들 수 있다는 것이 확실하다.
왜? 기존 확인된 값은 (1부터~확인된 값) 전체가 유효하므로 거기서 새로운 cash가 유효하다면 target+cash가 유효하다. 그런데 원래 비교값 초기값이 1로 설정돼 있으므로 target-1까지 유효하다. 그래서 다음 값인 target 값이 유효하기 위해서는 그 값에 해당하는 cash가 다음에 나와주어야 한다.
다음 비교에서 target 값보다 큰 값이 나올 경우 target값을 만들 방법이 없기 때문에 답이 target이 된다.