[이코테 Ch11-4] 만들 수 없는 금액 (그리디)

👩🏻‍💻문제설명

[이코테 Ch11-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(백만) 이하의 자연수다.

출력조건

• 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.

입력예시
5
3 2 1 1 9

출력예시
8

✍️Idea Sketch

문제 요약

N개의 동전
1원부터 양의 정수 금액을 만들 수 있는지 확인
만들 수 없는 양의 정수 금액 중 최솟값은?

시간복잡도

화폐 단위는 1,000,000 이하의 자연수 --> O(n)인 알고리즘으로 구현해야 함

1원, 2원, 3원, … 가장 큰 동전까지 양의 정수 금액을 만들 수 있는지 탐색한다. 입력 조건에서 화폐 단위는 최대 1,000,000이므로 O(n^2)으로 구현하면 1억을 한참 넘어 시간초과가 예상된다. 따라서 O(n)의 그리디한 알고리즘으로 구현해야함을 눈치챌 수 있다.

알고리즘 : 그리디

위에서 언급한 대로 O(n)의 그리디한 알고리즘으로 구현해야 한다. 창의력, 즉 문제를 풀기 위한 아이디어를 떠올리는 능력이 요구된다. 아이디어를 떠올리는 것은 매우 어렵지만, 막상 떠올리고 나면 구현은 쉬운 문제이다.

✍️내 소스코드

  import sys
  si = sys.stdin.readline

  n = int(si())
  coins = sorted(map(int, si().split()))
  cost = 0

  for coin in coins:
    if cost + 1 < coin:
      break
    else:
      cost += coin

  print(cost + 1)