만들 수 없는 금액 [Greedy] #이것이 코딩테스트다

[문제] 곱하기 혹은 더하기: 문제 설명

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다.이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.
예를 들어, N = 5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다.이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.
또 다른 예시로, N = 3 이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위) 동전이라고 가정합시다.이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

난이도: ●○○| 풀이시간 30m | 시간제한 1초 | 메모리 128mb

 

<input case>

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

 

 

<Output case>

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

 

input example	Output example
5 3 2 1 1 9	8

<Idea>

Q. 먼저 데이터를 큰 순서대로 정렬해준 이후 3가지의 케이스를 고려해보면 됩니다. 1.더했는데 목표값을 넘어버렸는가 2. 더했는데 값이 딱 맞았는가 3. 더했는데 여전히 작거나
A1. 데이터를 큰 순서대로 reverse = True로 정렬하는 가장 큰 이유는 작은 수부터 정렬하면 디테일을 잡을 수가 없어지기 때문입니다
예를들어 위 예시로 3을 만든다 가정하면 큰수는 9 -> 3으로 3에 도달하지만 작은 수부터 더해버리면 1+1+2로 3을 만들 수 없게 됩니다.
A2. 1번 케이스는 그냥 그 수를 무시해버리면 그만이고 2번 케이스는 반복문 종료시켜버리고 다음 수에 대해 고려하면 됩니다. 3번 케이스는 그 수를 더해두고 다음 수를 확인하러 가면 됩니다

 

n=int(input())
coins=list(map(int, input().split()))
coins.sort(reverse=True)
bool_=True #만들 수 있는지 없는지 판별하는 용도
res=0

while bool_: #만들 수 없는 금액 중 최솟값이므로 처음 발생할 때 멈춰주면 된다.
  res+=1
  if sum(coins) < res: break #만약 정말 운이 좋게도 모든 케이스가 다 만들어지는 금액이라면 처음으로 만들 수 없는 금액은 만들고 싶은 금액 +=1 이겠죠
  now=0 #반복문 내부에서 현재 금액을 담기 위한 변수
  for coin in coins:
    if coin + now > res: continue #만약에 동전을 소비 했는데 현재 값보다 크면 이 동전은 필요가 없습니다
    elif coin + now == res: 
      now+=coin
      break
    else: now += coin #만약 동전이 결과값보다 작다면 더해줘서 목표값에 더 가깝게 가야겠죠

  if now != res: bool_=False

print(res)