[이코테] 그리디 알고리즘 - 만들 수 없는 금액

N개의 동전이 주어졌을 때 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

📌 입력 조건

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

📌 출력 조건

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

 

📌입력 예시

5
3 2 1 1 9

📌출력 예시

8

---

📌풀이

# 1부터 target - 1까지 금액을 만들 수 있다고 가정, 화폐를 오름차순으로 정렬한다.
# 1을 만들 수 있는지 target = 1 부터 체크한다.

# 매번 target인 금액(현재 확인하는 동전의 단위가 target 이하인지)을 만들 수 있는지 확인한다.

# 현재 확인하는 동전의 단위가 target 미만이라면 target 금액을 만들 수 있고, 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)

사실 무슨 소리인지 몰라서 처음에 못 풀었다. 풀이를 참고했는데 일반적인 생각으로는 풀 수 없었다 하하..

그리디 알고리즘이 익숙하지 않아서 그런가 보다 하고 여러 번 반복 숙달시키면 되겠지 뭐

 

중요한 것은 1부터 target - 1까지의 금액을 만들 수 있다고 가정하는 것!

동전을 꺼낸 뒤 target 보다 작거나 같으면 target 이하의 금액을 만들 수 있다.

동전의 단위가 target보다 크다면 target 금액을 만들 수 없다.