# [이.취.코] Chap 11. 그리디 - Q4. 만들 수 없는 금액

- Author: @mildsalmon
- Published: 2021-09-07
- Updated: 2021-09-07
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-chap-11-%EA%B7%B8%EB%A6%AC%EB%94%94-q4-%EB%A7%8C%EB%93%A4-%EC%88%98-%EC%97%86%EB%8A%94-%EA%B8%88%EC%95%A1
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 그리디, 풀이, 만들수없는금액

---

# 1. 만들 수 없는 금액

- 난이도
	- 하
- 풀이 시간
	- 30분
- 시간 제한
	- 1초
- 메모리 제한
	- 128 MB
- 출처
	- K 대회 기출

### A. 문제

편의점 주인인 동빈이는 N개의 동전을 가지고 있다.   
N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하라.

##### a. 예를 들면. 

N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 동전이라고 가정하자. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.

N = 3이고 각 동전이 각각 3원, 5원, 7원이면, 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.

##### b. 입력 조건

- 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N
	- 1 <= N <= 1,000
- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수, 자연수는 공백으로 구분
	-  각 화폐 단위는 1,000,000 이하의 자연수

##### c. 출력 조건

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

##### d. 테스트 케이스

- 입력 예시

	```

	5
	3 2 1 1 9

	```

- 출력 예시

	```

	8

	```
	
### B. 내 답안

```python

n = int(input())  
array = list(map(int, input().split()))  
answer = []  
sum_ar = sum(array)  
for i in range(len(array)):  
    for j in range(i+1, len(array)+1):  
        answer.append(sum(array[i:j]))  

result = 1e9  
for i in range(1, sum_ar):  
    if i not in answer:  
        result = min(result, i)  
  
print(result)  
  
# 32분 53초 / Pass /

```

##### a. 회고

> 풀이

- 어떤 방식으로 풀어야할지 몰라서, 동전들로 만들 수 있는 금액을 전부 구했다. 그리고 동전으로 만들 수 있는 최대값을 정한 다음 거기에 없는 최초의 수를 반환하였다.

> 반성

-  '시간복잡도 초과할지도 모른다.'라기보다는 더 효율적인 그리디적 풀이가 있다.

> 결론

 - 그리디에 대해 더 많이 풀어볼 것.

### C. 문제 해설

정렬을 이용한 그리디 알고리즘으로 해결할 수 있다. 문제 해결을 위한 정확한 아이디어를 떠올리기 위해서는 충분히 고민을 해야 하는 문제이므로, 그리디 알고리즘에 익숙하지 않은 독자라면 문제 해결이 쉽지 않을 수 있다.

화폐 단위를 기준으로 오름차순으로 정렬한다. 이후 1부터 차례대로 특정한 금액을 만들 수 있는지 확인한다. 1부터 target-1까지의 모든 금액을 만들 수 있다고 가정하자. 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있다면, target 값을 증가시키는 방식을 이용한다.

그리디 알고리즘은 현재 상태에서 가장 좋아 보이는 것만 선택하는 알고리즘이다. 구체적으로 현재 상태를 **1부터 target-1까지의 모든 금액을 만들 수 있는 상태**라고 보자. 이때 매번 target인 금액도 만들 수 있는지(현재 확인하는 동전의 단위가 target 이하인지) 체크하는 것이다. 해당 금액을 만들 수 있다면, target의 값을 업데이트하면 된다.

![](https://static.blex.me/images/content/2021/9/8/8_YsVq1g3Cy5aANEwf1Vmq.jpg)

다시 말해, 현재 값을 다 더한 것까지는 동전을 조합해서 만들 수 있다. 따라서 **현재 값을 다 더한 것 + 1**이 만들 수 없는 최솟값이다. 즉 다음에 더하는 값이 **현재값의 합 + 1**보다 크면 만들 수 없는 값이 나온다.

##### a. 책 답안

[python-for-coding-test/4.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/11/4.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년