[Algorithm] 만들 수 없는 금액

문제

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

출력 조건

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

 

입력 예시

5
3 2 1 1 9

 

출력 예시

8

 

필자는 이 문제를 해결하기 위한 아이디어를 다음과 같이 생각해보았다.

 

1.

리스트의 최솟값 > 1 -> return 1

 

2.

if 리스트의 최댓값 < 해당값 이하의 나머지합 ->

리스트의 2번째 최댓값 < 해당값 이하의 나머지 합 ->

리스트의 3번째 최댓값 < 해당값 이하의 나머지 합 ->

(반복) ->

리스트의 n번째 최댓값 > 해당값 이하의 나머지 합 ->

return 해당값 이하의 나머지 합 + 1  

 

위 아이디어를 가지고 코드로 구현해보았다.

 

import sys

# k번째 최댓값을 구하는 함수
def kth_largest_number(arr, K):
    eigen_nums = set(arr)
    sorted_nums = sorted(eigen_nums, reverse=True)
    return sorted_nums[K - 1]


n = int(sys.stdin.readline().rstrip())
data = list(map(int, input().split()))
sum = 0
data.sort()

for i in range(0, len(data)):
    sum += data[i]

if data[0] > 1:
    print('1')

elif kth_largest_number(data, 1) > sum - kth_largest_number(data, 1):
    print(sum - kth_largest_number(data, 1) + 1)

else:
    minus = kth_largest_number(data, 1)
    for i in range(2, len(data) - 1):
        minus += kth_largest_number(data, i)  # 최댓값 + 2번째 최댓값 + ... + i번째 최댓값을 구하기 위한 변수
        if kth_largest_number(data, i) > sum - minus:  #
            print(sum - minus + 1)  # 전체합 - 변수(1번쨰, 2번쨰, ... i번째로 큰 값을 더한 값) + 1
            break
        else:
            continue

 

하지만 코드가 굉장히 난잡하다. 좀 더 간결하게 코드를 짤 순 없을까?

다음과 같은 아이디어를 살펴보자.

• 동전을 오름차순으로 정렬한다.
• 동전을 한개씩 추가하면서, target 값을 1부터 추가되는 동전금액을 합하면서 증가시킨다.
• 추가된 동전 금액이 target 값보다 작거나 같아야 추가된 동전 금액을 이용하여 그 target 값을 만들 수 있다.
• 추가된 동전 금액이 target 값보다 크다면 그 target 값이 만들 수 없는 최소 금액이다.

이 아이디어를 가지고 코드를 짜보면 다음과 같다.

 

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