[이것이 코딩 테스트다 with Python] Chapter 11. 그리디 - 만들 수 없는 금액

< 만들 수 없는 금액>

 

💬 문제 설명

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이떄 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

....

 

입력	출력
5   3 2 1 1 9	8

💬 입력 조건

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N ( 1 ≤ N ≤ 1,000 )
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분. 이때, 각 화폐의 단위는 1,000,000 이하의 자연수.

💬 출력 조건

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

---

✍ 문제요약

N객의 숫자들의 조합으로 만들 수 없는 숫자의 최솟값을 구하는 문제이다.  단순히 조합을 활용하면 쉽게 풀릴 수 있는 문제이나. 최대 1000개의 숫자가 주어지고, 1~1000개를 선택할 때의 조합을 모두 구한다면 시간 초과가 발생할 수 있다.

---

✅  문제 풀이

• 조합을 이용했을 시 시간초과가 발생할 수 있기 때문에 그리디하게 접근하자
• 만들 수 없는 최솟값을 구하는 문제이기에, 주어진 숫자 리스트를 오름차순한다.
• target = 1 : 만들고자 하는 숫자를 의미하고, 1을 만들 수 있는지 확인해보자,
• target = 1 일 때
  • 첫 번째 num = 1이고, num 이 target보다 크지 않으므로 1생성가능
  • target을 num + target인 2로 수정

• target = 2 일 때
  • 두 번째 num = 1이고, num 이 target보다 크지 않으므로 2생성가능
  • target을 num + target인 3로 수정
• target = 3 일 때
  • 세 번째 num = 2이고, num 이 target보다 크지 않으므로 3생성가능
  • 또한, 4도 생성가능( 이 전 target값 2에 num을 더하면 생성됨 )
  • target을 num + target인 5로 수정
• target = 5 일 때
  • 네 번째 num = 3이고, num 이 target보다 크지 않으므로 5생성가능
  • 또한, 6, 7도 생성가능 ( 이미 1,2,3,4 생성이 가능했기 때문)
  • target을 num + target인 8로 수정
• target = 8 일 때
  • 다섯 번째 num = 9이고, num 이 target보다 크므로 8생성 불가능
• 결과적으로 이 전에 생성 된 값들에서, 현재 더해줄 num 값을 더했을 때 target 값을 만들 수 있는 여부를 판단하는 과정이라 생각하자.

N = int(input())
lst = sorted(list(map(int,input().split())))

target = 1
for num in lst:
    if num > target:break     # 현재 숫자가 목표숫자보다 크면 정지
    else:target += num

print(target)