[알고리즘] 만들 수 없는 금액

문제

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

입력조건

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

출력조건

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

# 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력

n = int(input())
coins = list(map(int, input().split()))

coins.sort()

target = 1
for coin in coins:
  # 만들 수 없는 금액 찾았을 때 반복 종료
  if target < coin:
    break
  target += coin

# 만들 수 없는 금액 출력
print(target)

이코테 알고리즘 기출문제 풀면서
난이도가 1인데... 풀지를 못했다
set을 이용하나? 연결리스트를 이용하나? 시도하다가 도저히 못 풀겠어서
답안 코드를 봤다. 그래도 이해하는 데 넘 오래걸린...
주어진 코인으로 target 금액을 만들 수 있는지 체크한다.
=> 먼저 target = 1로 설정
정렬한 coins에서 꺼낸 coin이 target보다 크다면, 만들 수 없다.
같으면, 그 coin하나로 만들 수 있으므로 가능
작다면, 이미 target보다 작은 coin은 가능하다고 확인된 것이므로, 더하면 된다
그렇기 때문에 target < coin 조건만 확인하면 된다

비슷한 문제 - 백준 2437. 저울