문제
편의점 주인인 동빈이는 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 |
느낀점
이 문제는 처음 보면 그리디 알고리즘이라고 생각하기 힘든 문제였다.
하지만 알고나면 너무 쉬운 문제다.
하나의 유형이라고 생각하고 외워두면 좋을 것 같다.
문제를 풀어내는 사고방식은 다음과 같다.
작은 동전부터 탐색하면서, 만들고자 하는 금액(target)을 아직 이용하지 않고 가장 작은 금액의 동전이 만들고자 하는 금액 이하이면 해당 금액을 그 전에 이용한 동전과 조합해 만들 수 있다.
그 전에 이용했던 동전들로 1~target-1의 금액을 만들 수 있고 이용하지 않은 가장 작은 금액의 동전이 target 보다 작다면
이용하지 않은 가장 작은 금액의 동전 ( <= target) + (1~target-1) ∋ target
이 성립한다.
따라서 동전들을 정렬한 후, 하나씩 뽑으면서 다음 target을 업데이트해주면 된다.
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> v;
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
v.push_back(x);
}
// 1. 정렬
sort(v.begin(), v.end());
// 2. 첫번째 target은 1, 이용하기 전의 가장 작은 동전이 target이하여야 target을 만들 수 있다.
int target = 1;
for (int i = 0; i < n; i++) {
if (v[i] <= target) {
target += v[i];
}
else {
// 만들 수 없는 금액 종료
break;
}
}
cout << target << "\n";
return 0 ;
}'알고리즘 > 오답노트' 카테고리의 다른 글
| [Algorithm][오답노트][이코테] 45. 최종 순위 (0) | 2022.01.16 |
|---|---|
| [Algorithm][오답노트][이코테] 42. 탑승구 (0) | 2022.01.16 |
| [Algorithm][Leetcode] 208. Implement Trie (Prefix Tree) (0) | 2021.10.17 |
| [Algorithm][LeetCode] 1293. Shortest Path in a Grid with Obstacles Elimination (0) | 2021.09.28 |
