[이코테 기출] 만들 수 없는 금액

🦥 만들 수 없는 금액

문제

동네 편의점의 주인인 동빈이는 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
  

풀이

🔎 아이디어

• 정렬 + 그리디 알고리즘 적용
• 1부터 차례대로 특정한 금액을 만들 수 있는 확인
  • 처음에는 금액 1을 만들 수 있는지 확인 → target = 1
  • target = 1을 만족하는지 확인 → target = 1 + 1 = 2 update
  • target = 2를 만족하는지 확인 → target = 2 + 2 = 4 update
  • target = 4를 만족하는지 확인 → target = 4 + 3 = 7 update
  • target = 7을 만족하는지 확인 → 8인 동전이 있으므로, 7을 만드는 방법은 없음
  • 만들 수 없다면 종료

🔎 코드

# 만들 수 없는 금액
x = int(input())

list_x = list(map(int, input().split()))
list_x.sort()

money = 1
for i in list_x:
    # 만들 수 없는 금액이 있다면 종료
    if money < i:
        break
    money += i
print(money)