[그리디-문제] 만들 수 없는 금액

<입력조건>

첫째 줄에는 동전의 개수를 나타내는 양의 정수 n이 주어집니다. (1 <= n <= 1,000)

둘째 줄에는 각 동전의 화폐 단위를 나타내는 n개의 자연수가 주어지며, 각 자연수는 공백으로 구분

이때, 각 화폐 단위는 1,000,000 이하인 자연수

 

<출력조건>

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

 

 

---

<아이디어>

1부터 시작해서 만들 수 없는 최솟값을 찾기 때문에 그리디 알고리즘이다.

만들 수 있는 정수인지 아닌지 판별하는 방법은 다음과 같다.

 

1. 입력받은 동전들을 오름차순으로 정렬

2. 먼저 target정수를 1로 설정

3. 첫번째 동전부터 시작해서 마지막 동전까지 반복문을 도는데, 현재 target보다 크면 빠져나오고 그렇지 않으면 target+=동전 을 해준다

 

 

예를 들어

1, 2, 3 ,8 동전이 있으면

 

-target = 1

1(target) < 1(현재 동전) 이 아니므로 

target = 1 + 1 = 2

 

-target = 2

2 < 2 이 아니므로

target = 2 + 2 = 4

 

-target = 4

4 < 3 이 아니므로

target = 4 + 3 = 7

 

-target = 7

7 < 8 이므로 반목문을 빠져나옴!

 

최종 target = 7

 

이 문제의 해설을 보면서 가장 이해가 가지 않았던 부분은

 

1. 왜 target이 현재의 동전보다 작으면 만들 수 없는 화폐 단위인지??

2. 왜 target이 현재의 동전보다 크거나 같으면 만들 수 있는 화폐 단위인지??

3. target+=현재의 동전 을 해서 나온 값에서 -1인 값까지 왜 만들 수 있는 화폐단위인지??

 

1. target보다 -1인 숫자까지 만들 수 있는 상황에서 현재의 동전보다 작다면 target은 만들 수 없게 되므로 target이 결과이다

2. 이미 (target-1)까지 만들 수 있는 상황에서 target보다 작으면 이미 만들 수 있는 숫자이고 target과 같으면 현재까지 만들 수 있는 최대값이 된다

3. target값은 이미 (target-1)까지 가능하다는 가정에서 출발했다.