[이코테] 그리디 문제 04 - 만들 수 없는 금액

문제

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

출력 조건

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

해결

접근 1

우선 동전은 입력된 화폐를 입력된 개수만큼 사용하는 상황이고, 이 동전들을 활용해서 만들 수 있는 양의 정수 금액 중 최솟값을 찾는 것이기 때문에, 1원부터 차례대로 올라가면서 금액을 만들 수 있는지 없는지 판단한다.

내가 세운 로직은 다음과 같다.

1. 최솟값이므로 입력받은 코인들을 오름차순 정렬한 뒤, 맨 앞 코인부터 순차적으로 금액 리스트에 추가한다.
2. 금액 리스트에 코인을 추가했으면, 원래 존재하는 금액 리스트들의 금액에 추가한 코인의 가격만큼을 더한 금액들을 또 추가해준다.
3. 이를 끝까지 반복한 뒤, 중복값들을 집합 자료형을 통해 삭제한다.
4. 1로 선언된 cnt 변수와 오름차순 정렬된 금액 리스트를 동시에 하나씩 올려, cnt와 달라질 때 cnt원의 금액이 없다고 판단한다.

파이썬으로 작성한 코드는 다음과 같다.

코드 1

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

def find_blank(arr):
  cnt = 1
  for num in arr:
    if num != cnt:
      print(cnt)
      return
    cnt += 1

possible = []
for coin in coins:
  possible.append(coin)
  for p in range(len(possible) - 1):
    possible.append(possible[p] + coin)

possible = list(set(possible))
find_blank(possible)

접근 2 (본 책 답안)

근본적인 로직은 비슷하지만 해당 코드가 다소 떠올리기는 쉽지않은 느낌이다.

먼저 화폐를 오름차순 정렬한 뒤 만들 수 없는 화폐 단위를 target이라는 변수로 지정, target을 1부터 올려가며 작은 단위 원소부터 해당 금액을 만들 수 있는지 확인한다.

구체적인 과정을 예시로 들면 이해하기 편리하다.

먼저 1, 2, 3을 가지고 화폐를 만들어보자.

• 1원 : 1
• 2원 : 2
• 3원 : 3
• 4원 : 1 + 3
• 5원 : 2 + 3
• 6원 : 1 + 2 + 3

이렇게 1 ~ 6까지의 숫자를 모두 만들어낼 수 있다.

그럼 동전 5를 여기에 추가하면 몇 원까지 만들 수 있는지 바로 알아맞혀보자. 당연하게도 11원까지의 숫자를 모두 만들 수 있다. 현재 만들 수 있는 1원, 2원, … , 6원에 5원씩을 더하면 6원, 7원, … , 11원이 되는 것이기 때문이다.

그럼 이 상황에 X원을 추가하면? 마찬가지로 1~11원에 1+X ~ 11+X만큼이 추가가 될 것이다. 그럼 결국 만들지 못하는 화폐는 이 1+X가 11원의 다음값인 12원보다 커서 연결이 안될 때라고 볼 수 있다.

즉 1 + X > 12, X > 11이고, X가 12일 때 흐름이 끊기고 끊긴 target은 12가 된다.

뭐.. 그래서 근본적인 로직은 내가 접근한 방식인 접근 1과 비슷하다고 한 것이다. 코인을 금액 리스트에 추가한 뒤 원래 있던 금액 리스트의 값들에 코인만큼을 더한 값을 추가로 더하는 것이니 말이다.

하지만 결국 간결하고 근본을 꿰뚫은 코드는 접근 2를 통한 코드 2이다. 정답은 다음과 같다.

코드 2 (본 책 답안)

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)