[그리디 Greedy] 04. 만들 수 없는 금액 / 파이썬

그리디 (Greedy)

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

---

만들 수 없는 금액

난이도 ★☆☆  풀이시간 30분  시간제한 1초

 

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

---

모범코드

# 동전의 개수
n = int(input())
# 동전 종류
coins = list(map(int, input().split()))
# 오름차순 정렬
coins.sort()

# 만들고자 하는 금액 (1부터 확인)
target = 1

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


print(target)

---

 

해설

정렬을 이용한 그리디 알고리즘

• 화폐 단위를 기준으로 오름차순 정렬
• 1부터 차례대로 금액을 만들 수 있는지 확인

 

step 0 (초기 단계)

coins = [동전 1, 동전 1, 동전 2, 동전 3, 동전 9] 

target = 1

 

 

step 1 (동전 1)

coin = 1 (현재 확인중인 동전)

target = 1 (만들고자 하는 금액)

 

동전 1을 이용하여 금액 1을 만들 수 있는가? 

금액 1을 만들 수 있는지의 여부는 동전 1에 달렸다.

동전 1이 금액 1 이하이기 때문에 만들 수 있다.

현재 만들 수 있는 금액	새로운 동전 1을 이용하여 만들 수 있는 금액
	1

 

step 1 수행 결과

사용한 동전 : 동전 1

만들 수 있는 금액 : 1

 

그 다음 확인할 목표 금액(target) 갱신 : 현재 target - 1까지는 만들 수 있다. 

target

= target + coin

= 1 + 1

= 2 

 

 

step 2 (동전 1)

coin = 1

target = 2

 

동전 1을 이용하여 금액 2를 만들 수 있는가?

동전 1이 금액 2 이하이기 때문에 만들 수 있다.

현재 만들 수 있는 금액	새로운 동전 1을 이용하여 만들 수 있는 금액
1	1 + 1 = 2

 

step 2 수행 결과

사용한 동전 : 동전1, 동전1

만들 수 있는 금액 : 1, 2

 

그 다음 확인할 목표 금액(target) 갱신 : 현재 target - 1까지는 만들 수 있다.

target

= target + coin

= 2 + 1

= 3 

 

 

step 3 (동전 2)

coin = 2 (현재 확인중인 동전)

target = 3 (만들고자 하는 금액) 

 

동전 2를 이용하여 금액 3을 만들 수 있는가?

동전 2가 금액 3 이하이기 때문에 만들 수 있다.

현재 만들 수 있는 금액	새로운 동전 2를 이용하여 만들 수 있는 금액
1	1 + 2 = 3
2	2 + 2 = 4

 

step 3 수행 결과

사용한 동전 : 동전1, 동전1, 동전2

만들 수 있는 금액 : 1, 2, 3, 4

 

그 다음 확인할 목표 금액(target) 갱신 : 현재 target - 1까지는 만들 수 있다.

target

= target + coin

= 3 + 2

= 5

 

 

step 4 (동전 3)

coin = 3 (현재 확인중인 동전)

target = 5 (만들고자 하는 금액) 

 

동전 3을 이용하여 금액 5를 만들 수 있는가?

동전 3이 금액 5 이하이기 때문에 만들 수 있다.

현재 만들 수 있는 금액	새로운 동전 3을 이용하여 만들 수 있는 금액
1	1 + 3 = 4
2	2 + 3 = 5
3	3 + 3 = 6
4	4 + 3 = 7

 

step 4 수행 결과

사용한 동전 : 동전1, 동전1, 동전2, 동전3

만들 수 있는 금액 : 1, 2, 3, 4, 5, 6, 7

 

그 다음 확인할 목표 금액(target) 갱신 : 현재 target - 1까지는 만들 수 있다.

target

= target + coin

= 5 + 3

= 8

 

 

step 5 (동전 9)

coin = 9 (현재 확인중인 동전)

target = 8 (만들고자 하는 금액)

 

동전 9를 이용하여 금액 8을 만들 수 있는가?

동전 9가 금액 8보다 크기 때문에 만들 수 없다.

 

현재 target이 만들 수 없는 금액(답)이 된다. 

 

 

---

참고

2021.07.13 - [자료구조 알고리즘] - [알고리즘] Greedy Algorithm 탐욕 알고리즘 / 파이썬

[알고리즘] Greedy Algorithm 탐욕 알고리즘 / 파이썬

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년