[이코테] 만들 수 없는 금액

문제

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

출력

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

예제

Example 1:

Input: 
5
3 2 1 1 9
Output: 
8

조건

시간 제한 : 1초

메모리 제한 : 128 MB

풀이과정

내 풀이

import sys
from itertools import combinations
n = int(sys.stdin.readline())
s = list(map(int,sys.stdin.readline().split(' ')))
s.sort()
res = []
target = 1

while(1):
  find = 0
  for i in range(len(s)):
    li = list(combinations(s,i+1))
    for j in range(len(li)):
      sum = 0
      for k in range(len(li[j])):
        sum += li[j][k]
        if sum == target:
          find = 1
          target += 1
          break
      
  if find == 0:
    print(target)
    break

맞는 풀이같지는 않다. 그래도 어떻게든 해결하려고 노력을 했다. 우선 작은 순서대로 sort를 한 뒤, 부분집합이 작은 수부터 비교해나가면서 target과 맞지 않는다면 조건문을 나오게 되고 답을 출력한다.

책 풀이

이 문제는 정렬을 이용한 그리디 알고리즘으로 해결할 수 있는 문제이다.

문제 해결 아이디어는 다음과 같다. 일단 동전에 대한 정보가 주어졌을 때, 화폐 단위를 기준으로 오름차순 정렬한다. 이후에 1부터 차례때로 특정한 금액을 만들 수 있는지 확인하면 된다. 1부터 target-1까지의 모든 금액을 만들 수 있다고 가정해보자. 우리는 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있다면, target 값을 업데이트하는(증가시키는) 방식을 이용한다.

기본적으로 그리디 알고리즘은, 현재 상태에서 매번 가장 좋아 보이는 것만을 선택하는 알고리즘이라고 하였다. 구체적으로 현재 상태를 ‘1부터 target - 1까지의 모든 금액을 만들 수 있는 상태’라고 보자. 이때 매번 target인 금액도 만들 수 있는지(현재 확인하는 동전의 단위가 target 이하인지) 체크하는 것이다. 만약 해당 금액을 만들 수 있다면, target의 값을 업데이트(현재 상태를 업데이트)하면 된다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1

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

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

느낀점

뭔가 생각은 비슷한데 코드가 훨씬 간단하다. 이해가 되는 듯 안되는 듯 애매하다. 계속 봐야할 듯함.

비슷한 문제

BOJ-저울