문제 출처
- 이것이 취업을 위한 코딩테스트다 with 파이썬
- Chapter 11 - 그리디 4. 만들 수 없는 금액
제한
- 시간 제한 : 1 초
- 메모리 제한 : 128 MB
문제
- 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.
- 예를 들어 N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리 동전이라고 가정하면 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.
입력
- 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다.(1 <= N <= 1,000)
- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 이때 각 화폐 단위는 1,000,000 이하의 자연수이다.
출력
- 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.
👀 풀이
- 처음에는 bool 배열을 만들어서 N개의 동전들로 가능한 조합들을 구한 다음 그 조합들의 누적합을 각각 구해서 만들 수 있는 숫자를 체크했다. 그러면 부분 집합에서 생기지 않은 합의 인덱스에는 체크가 되지 않았을 것이니까 해당 인덱스는 false로 남아있을 것이다. false인 인덱스 중에서 가장 작은 값을 출력했다.
- 근데 이렇게 작성하고 디버깅을 해 보니까 중복되는 조합이 넘 많이 만들어져서 같은 숫자가 나오는 연산이 반복되었다. 그래서 좀 비효율적인 것 같아서 정답코드를 참고했다.
- 책에 있는 정답 풀이는
target이 될 숫자를 정한 다음 해당 숫자를 만들 수 있다면 target값을 업데이트하고 그렇지 않다면 마지막에 구한 target값이 정답이 되는 것이다.
코드
