코테/Greedy
[C/C++] 나동빈 만들 수 없는 금액, Greedy
상똥
2023. 2. 7. 16:59
문제
동빈이는 N개의 동전을 가지고 있다. N개의 동전의 단위(1,000,000이하의 자연수)를 입력받고, 이 N개의 동전을 조합하여 만들 수 없는 정수 중 최솟값을 구하라. 예를 들어 N=5이고 각 단위가 3, 2, 1, 1, 9일 때 만들 수 없는 정수의 최소 단위는 8이다. (N은 1,000보다 작거나 같은 자연수) |
코드
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> coin;
int N, num, result=1;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> num;
coin.push_back(num);
}
sort(coin.begin(), coin.end());
num = 1;
while (1) {
for (int i = N - 1; i > -1; i--)
if (coin[i] <= num)
num -= coin[i];
if (num == 0)
num = ++result;
else
break;
}
cout << result;
}
풀이
1. 숫자를 증가시켜가며 비교할 변수 num과 result=1를 선언한다.
2. 입력받은 동전들을 오름차순으로 정렬하고, for문을 사용해 가장 높은 동전 단위부터 num과 비교한다.
3. coin[i]번째 값이 num보다 작거나 같으면 num-=coin[i]
4. coin[i]번째 값이 num보다 크다면 그 다음으로 큰 동전 단위로 넘어간다
5. for문이 끝났을 때 num=0이면 입력받은 동전들로 조합이 가능한 수이므로, result의 값을 증가시켜 num에 저장한다.
6. num값이 0이 아니라면 입력받은 동전들로 조합이 불가능한 것이므로, num을 출력하고 종료한다.