문제 설명

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

출력

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

문제 풀이

고민

일단 낮은 금액으로 정렬하고... 낮은 인덱스부터 확인해나가면 될 것 같은데,
인덱스 당 모든 경우를 먼저 확인하고 없는 금액을 찾기 보다는 최소 금액부터 채워나가는 방식으로 하는게 맞는 것 같았다.

접근은 맞았지만 어떻게 구현할까 많이 헤매다가, 결국 답을 봤다.

구현 방법

최소 금액 타겟을 설정하고, 갱신 방법은 단순히 인덱스 값을 더해주며 타겟을 늘려가면 된다.(낮은 인덱스 값부터 더해 가면 포함할 수 있는 최소 값들을 다 포함하기 때문)

맞은 코드

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)

target=1로 선언하는 방법이 신박했다. 기억하자

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음