[이.코.테] chap11. 그리디 - 만들 수 없는 금액

*이것이 취업을 위한 코딩테스트다 with 파이썬 교재를 공부한 내용을 바탕으로 작성했습니다.

 

 

 

그리디

: 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘,  '최적의 해' 찾기 문제.

대표문제) 거스름돈, 1이 될 때까지

 

 

 

 

만들 수 없는 금액

 

 

1. 문제

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

---

2. 입력 예시

5

3 2 1 1 9

---

3. 출력 예시

8

---

 

 

 

- 이 문제는 그냥 처음부터 접근하는 게 어려웠다.. 생각할수록 계속 어려운 알고리즘 밖에 생각나지 않아서 결국 해답을 봤다.. 

답을 봤는데도 잘 이해되지 않는 문제였다.

 

우선 만들 수 없는 최솟값을 구해야 하므로 리스트를 정렬한다.

해답에서는 target을 이 금액을 만들 수 있는 가 없는 가를 확인하는 기준점으로 두었다.

입력 예시를 예를 들어 설명해보자면, 우선 맨 처음에 target=1로 두고 1을 만들 수 있는가, 없는 가를 확인한다.

 

 

target = 1 (1을 만들 수 있는 지 확인)

-> 첫 번째 동전이 1이므로 target을 만들 수 있다.

-> target = 1 + 1로 증가

-> 1까지의 수 만들 수 있음

현재 만들 수 있는 금액	첫 번째 동전 1로 만들 수 있는 금액
0	1

 

 

target = 2 (2를 만들 수 있는 지 확인)

-> 두 번째 동전이 1이므로 target인 2를 만들 수 있다.

-> target = 2 + 1로 증가

-> 1~2까지의 수 만들 수 있음 

현재 만들 수 있는 금액	두 번째 동전 1로 만들 수 있는 금액
1	1 + 1 = 2

 

 

target = 3 (3을 만들 수 있는 지 확인)

-> 세 번째 동전이 2이므로 target인 3을 만들 수 있다.

-> target = 3 + 2로 증가

->  1 ~ 4까지의 수 만들 수 있음

현재 만들 수 있는 금액	세 번째 동전 2로 만들 수 있는 금액
1	1 + 2 = 3
2	2 + 2 = 4

 

 

target = 5 (5를 만들 수 있는 지 확인)

-> 네 번째 동전이 3이므로 target인 5를 만들 수 있다. 

-> target = 5 + 3

-> 1 ~ 7까지의 수 만들 수 있음

현재 만들 수 있는 금액	네 번재 동전 3으로 만들 수 있는 금액
1	1 + 3 = 4
2	2 + 3 = 5
3	3 + 3 = 6
4	4 + 3 = 7

 

 

target = 8 (8을 만들 수 있는 지 확인)

-> 네 번째 동전인 9가 target인 8보다 크므로 만들 수 없다.

-> 9가 추가되면 최소로 만들 수 있는 금액이 9이고 10, 11...16이다. 따라서 8은 만들 수가 없다.

 

 

 

코드)

 

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)

 

 

이 문제는 다음에 다시 혼자 힘으로 풀어보도록 하자..!!

 

 

참고)

https://devmath.tistory.com/88

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