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

이것이 취업을 위한 코딩테스트다 with 파이썬 책을 읽고 정리한 내용입니다.

 

 

 

 

📋 문제

동네 편의점의 주인인 동빈이는 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 이하의 자연수이다.

 

 

👈 출력

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

 

 

📝 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))
answer = 1

for num in arr:
  if answer < num:
    break
  answer += num
print(answer)

 

주어진 수로 만들 수 없는 수 중 최솟값을 출력하는 문제이므로 먼저 입력받은 수가 들어있는 리스트인 arr을 오름차순 정렬한다.

 

그 다음 arr을 순회하며 요소들을 answer에 더해나간다.

answer를 1로 초기화한 이유는 양의 정수 중 최솟값이 1이기 때문이다.

 

제일 작은 요소부터 더해나가다 arr의 특정 요소보다 answer의 값이 작을 때가 오면 이때 answer에 담겨있는 수는 arr의 요소들로 만들 수 없는 수이다.

따라서 이 경우 for문의 순회를 멈추고 answer를 출력한다.

 

단순히 거스름돈과 비슷한 유형의 문제인 줄 알았다가 풀이에 애먹었던 문제였다.

이러한 유형의 그리디 문제를 더 풀어봐야 할 것 같다.

 

 

🔍 참조

이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 나동빈)