[ 그리디 ] 04 만들 수 없는 금액

난이도 : 하 풀이시간 : 30분 시간제한 : 1초 기출 : K 대회 기출

[ 그리디 ] 04 만들 수 없는 금액

동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어 N = 5이고, 각 동전이 3, 2, 1, 1, 9원짜리 동전이라고 가정할 때,
만들 수 없는 양의 정수 금액 중 최솟값은 8원 입니다.

 

:: 입력 조건

 

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

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

이때 각 화폐단위는 1,000,000 이하의 자연수 입니다.

 

:: 출력 조건

 

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

 

---

 

  내   코드  

 

아이디어를 생각못해서 답지 봄

 

  정답  코드  

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n = 0;
	cin >> n;

	vector<int> nums;

	for(int i=0; i<n; i++){
		int k = 0;
		cin >> k;
		nums.push_back(k);
	}

	sort(nums.begin(), nums.end());

	int p = 1;

	for (int i = 0; i < n; i++) {
		if (p >= nums[i]) {
			p += nums[i];
		}
		else break;
	}

	cout << p;
	return 0;
}

 

  리뷰  

1원부터 해당 금액을 만들 수 있는지 체크함

 

int p = 1;

	for (int i = 0; i < n; i++) {
		if (p >= nums[i]) {
			p += nums[i];
		}
		else break;
	}

이 부분인데 p=1 이고 nums[0] 이 1이 아닌 경우 1을 만들 수 없다는 뜻이기 때문에 바로 반복문이 종료됨

 

예시 입력 [ 3 2 1 1 9 ] 기준 

p=1 이고 nums[0]=1  --> 1을 만들 수 있고, p+=nums 로 p=2가 됨

p=2 이고 nums[1]=1  -->  1은 2보다 작기때문에 그 전의 1과 더해서 2을 만들 수 있고, p+=nums로 p=3이 됨

p=3 이고 nums[2]=2  -->  2는 3보다 작고 그 전의 수와 더해서 3을 만들 수 있고, p+=nums로 p=5가 됨

p=5 이고 nums[3]=3  -->  3는 5보다 작고 그 전의 수와 더해서 5를 만들 수 있고, p+=nums로 p=8이 됨

p=8 이고 nums[4]=9  -->  9는 8보다 크기 때문에 8은 만들 수 없고, 반복문이 종료됨