[이취코] 알고리즘 유형별 기출문제: 그리디 - 4. 만들 수 없는 금액 (Python)

4. 만들 수 없는 금액

문제

• 동네 편의점 주인인 동빈이는 N개의 동전을 갖고 있음. N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.

예시

• N=5이고 각 동전이 각각 3/2/1/1/9원짜리 동전이면, 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원임.
• N=3이고 각 동전이 3/5/7원짜리 동전이면, 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원임.

입출력 조건

• 입력
  • 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어짐 (1 ≤ N ≤ 1,000)
  • 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분함. 이때 각 화폐 단위는 1,000,000 이하의 자연수임
• 출력
  • 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력

풀이

동전의 크기를 오름차순으로 정렬한 후 1부터 차례대로 만들 수 있는지 없는지 검사하기 (target = 1에서 시작)

1, 2, 3이 있으면 1~6을 만들 수 있음.

5도 있다면 6~11도 만들 수 있음.

1 ~ (target-1)을 만들 수 있을 때 새로운 동전 x가 주어진다면 1+x ~ (target-1)+x을 만들 수 있음

target보다 x가 크면 target부터 x 사이의 수는 만들 수 없으므로 target < x면 break

 

시간 복잡도: O(nlogn) (정렬)

공간 복잡도: O(1) (target, x 변수 2개만 추가적으로 사용)

N = int(input())
coin = list(map(int, input().split()))
coin.sort()
target = 1
for x in coin:
    if target < x:
        break
    target += x
    print(target)
print(target)

• 거스름돈 문제와의 차이점: 거스름돈 문제는 어떤 종류에 해당하는 동전의 개수가 무한한 반면 (ex. 1원짜리 동전 무한개, 2원짜리 동전 무한개 …) 이 문제는 동전의 종류 뿐만 아니라 동전의 개수도 제한되어 있음