🚨 ‘이것이 취업을 위한 코딩테스트다’ 교재 정리

문제

N개의 동전이 주어질 때 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.

입력 조건

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

출력 조건

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

입력 예시

입력

1
2
5
3 2 1 1 9

출력

1
8

풀이

아이디어

  • target 금액은 1부터 시작하고 화폐 단위는 오름차순 정렬을 수행한다.
  • 화폐단위를 순차적으로 검사하면서 만약 target보다 단위가 작을 경우 해당 target은 만들 수 있다.
  • target을 만들 수 있을 경우, 다음 target은 해당 화폐단위를 더한 값으로 갱신한다.
  • target보다 큰 값이 검사 단위로 주어질 경우 해당 target은 만들지 못한다고 판단되어 답으로 출력한다.

핵심은 target 이하의 값은 모두 만들 수 있다고 정의하는 것이었다. 화폐 단위가 작은 동전부터 하나씩 확인하면서 target을 증가시키고 가장 작은 target 값을 찾아가기 때문에 그리디 알고리즘으로 분류된다.

1
2
3
4
5
6
7
8
9
10
n = int(input())
coin = list(map(int, input().split()))
coin.sort()
target = 1
for c in coin:
    if c <= target:
        target+=c
    else:
        break
print(target)