문제

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

예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라 가정하면, 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.

또 다른 예시로, N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리 동전이라 가정하면, 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.

입력 조건

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

출력 조건

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

Test Case

// 입력 예시
5
3 2 1 1 9

// 출력 예시
8

접근

• 처음엔 오름차순 정렬 후 동전 종류끼리 일일이 다 더해가는 방식으로 접근해야하나 싶었다.(조합 방식)
  → 굉장히 비효율적인 방식이다.
• 맨 처음 동전부터 차례대로 동전을 추가해가며 만들 수 없는 금액을 찾는 방식으로 접근해야 한다.
• 단순히 동전을 화폐 단위 기준으로 정렬한 뒤, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target 변수를 업데이트하는 방법으로 최적의 해를 계산할 수 있다.
• 만들 수 없는 금액을 찾았을 때 루프를 종료한다.
• 이해가 안된다면 참고하자.

내 코드

n = int(input())
coins = list(map(int, input().split()))
coins.sort()
target = 1
for i in coins:
	if target < i:
    	break
    target += i
    
print(target)