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

@mildsalmon·2021-09-08 08:17

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. 내 답안


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의 값을 업데이트하면 된다.