[Greedy] 이코테 “만들 수 없는 금액” Python 풀이

문제

• 동네 편의점의 주인인 동빈이는 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

풀이

• 최대한 이해가 잘 되도록 정리해보겠습니다.
• 3, 2, 1, 1, 9를 오름차순 정렬하면 1, 1, 2, 3, 9가 됩니다.
• 정렬한 동전을 순서대로 확인하며, 만들 수 있는 숫자를 확인합니다.
  • 만들 수 없는 최솟값을 확인하는 것과 동일한 의미입니다.
• 만들 수 있는 숫자는 1부터 확인하고, 이를 목푯값으로 지정합니다.
• 목푯값 1은 첫 번째 동전 1과 같으므로, 생성할 수 있습니다.
  • 따라서, 목푯값 1에 동전 1을 더해, 목푯값을 2로 수정합니다.
• 목푯값 2는 두 번째 동전 1보다 크므로 생성할 수 있습니다.
  • 기존에 만들 수 있는 동전인 1에 동전 1을 더하므로, 2를 생성할 수 있습니다.
  • 따라서, 목푯값 2에 동전 1을 더해, 목푯값을 3으로 수정합니다.
• 목푯값 3은 세 번째 동전 2보다 크므로 생성할 수 있습니다.
  • 기존에 만들 수 있는 동전인 1, 2에 동전 2을 더하므로, 3, 4를 생성할 수 있습니다.
  • 따라서, 목푯값 3에 동전 2를 더해, 목푯값을 5로 수정합니다.
• 목푯값 5는 네 번째 동전 3보다 크므로 생성할 수 있습니다.
  • 기존에 만들 수 있는 동전인 1, 2, 3, 4에 동전 3을 더하므로, 4, 5, 6, 7을 생성할 수 있습니다.
  • 따라서, 목푯값 5에 동전 3을 더해, 목푯값을 8로 수정합니다.
• 목푯값 8은 다섯 번째 동전 9보다 작으므로 생성할 수 없습니다.
  • 기존에 만들 수 있는 동전인 1, 2, 3, 4, 5, 6, 7에 동전 9을 더하므로, 10 ~ 16을 생성할 수 있습니다.
• 따라서, 만들 수 없는 최솟값은 8이 됩니다.

예제 코드

import sys

n = int(sys.stdin.readline())
coins = list(map(int, sys.stdin.readline().rstrip().split()))

# 동전 오름차순 정렬
coins.sort()

# 목푯값 설정
target = 1
# 동전 탐색
for coin in coins:
    # 현재 동전이 못푯값보다 크다면, 해당 목푯값은 만들 수 없음
    if (coin > target):        
        break
    # 목푯값 갱신
    target += coin

# 만들 수 없는 목푯값 출력
print(target)

참고

• 이것이 취업을 위한 코딩 테스트다. with python