[이것이 코딩테스트다] Chapter11. Q4 만들 수 없는 금액
문제
동네 편의점 주인인 표표는 N개의 동전을 가지고 있습니다. 이 때 N개의 동전을 이용해서 만들 수 없는 양의 정수 금액 중 최솟값을 구하시오.
예시
N=5이고, 각 동전이3, 2, 1, 1, 9원일 때, 만들 수 없는 양의 금액 중 최솟값은8원이다.
입력 조건
- 첫째 줄엔 동전 개수를 나타내는 양의 정수 N이 주어진다.
(1<=N<=1,000)- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 각 화폐 단위는
1,000,000이하의 자연수이다.
출력 조건- 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.
Problem Solving
먼저 화폐단위가 든 리스트를 오름차순으로 정렬하고, 1부터 차례대로 특정한 금액을 만들 수 있는지 확인한다. 화폐단위를 작은거부터 빼내서 더하면 현재 금액을 만들 수 있는지 체크할 수 있다.현재 상태에서 매번 가장 좋아보이는 것만을 선택 하는 그리디 알고리즘을 이용한 문제라는 것을 인식하면 편하게 문제를 해결할 수 있다. 현재 상태 = [1부터 target-1까지 모든 금액을 만들 수 있는 상태]라고 하고 이때 매번 target을 만들 수 있는지(target이 현재 확인하는 동전 단위보다 작으면 target을 만들 수 없다) 체크하고 가능하면 target 값을 업데이트한다.
예시로 n=4 1 7 3 1이 입력값으로 주어졌다고 생각해본다.
-
값을 저장한 리스트를 정렬하고,
target = 1로 설정한다. -
target = 1을 만족하는지 확인한다. 현재 확인하는 동전 단위인(data[0]=1) <= target이므로 가능하다.target += data[0]로 업데이트한다. -
target = 2를 만족하는지 확인한다. 1은 이전 단계에서 만들 수 있는 금액임을 확인했고 현재 확인하는 동전 단위인(data[1]=1) <= target이므로 가능하다.target += data[1] -
target = 3을 만족하는지 확인한다. 현재 확인하는 동전 단위가(data[2]=3) <= target이므로 만족한다.target += data[2]로 현재 target이 6으로 업데이트되고 이는 5까지의 모든 금액을 만들 수 있다는 말이다. -
target = 6을 만족하는지 확인한다. 현재 확인하는 동전 단위가(data[3]=7) <= target으로 만족하지 않으므로 금액 6을 만드는 방법은 없다. 정답은 6이 된다.
Python Code
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)Discussion
그리디 알고리즘에 관한 문제임을 알고 있음에도 30분이라는 시간 내에 코드를 완성하지 못했다. 처음 문제를 보고 data에 해당하는 모든 원소들의 집합을 확인하기 위해 set 함수를 사용해야하는지, 노가다로 모든 집합의 합을 알아봐야하는지 고민했다. 해설을 찾아보고도 이해하는데 오랜 시간이 걸렸는데 이는 target에 현재 확인하는 화폐 단위를 더해가면서 업데이트를 하면 그 이하의 금액이 완성이 가능하다는 것을 바로 눈치채지 못했기 때문이다. 문제를 최대한 작게 만들어서 푼 해가 전체의 해가 될 수 있다는 것을 염두해두면서 문제를 풀어야한다.
References
- 나동빈, ⌜이것이 취업을 위한 코딩테스트다 with Python⌟, 한빛미디어, 2020, p.314
