X - [ 그리디 ] 만들 수 없는 금액 - R

난이도 : 하  풀이시간 : 30/27  시간제한 : 1초  기출 : k 대회 기출

[ 문제유형 ] 문제번호 문제제목

 

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수

 

금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

예를 들어, N = 5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다.

 

이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

 

또 다른 예시로, N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위_ 동전이라고 가정합시다.

 

이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

 

:: 입력 조건

 

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

 

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

 

:: 출력 조건

 

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

 

 

---

  아이디어  

틀림 ,, 저번에도 틀렸는데

바보멍충이

 

정답아이디어 정리해놓아야지

1. 동전의 가치를 입력받아서 벡터에 저장

2. 정렬

3. target 을 1로 설정

4. 동전의 개수만큼 반복문을 돌면서

target과 해당 인덱스의 값을 비교하고 

만약 target이 해당 인덱스의 값보다 작으면 반복문을 끝내고

그렇지 않으면 해당 인덱스의 값을 더해준다.

 

  내   코드  

 

 

  정답  코드  

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

int main(void) {
    cin >> n;

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

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

    int target = 1;
    for (int i = 0; i < n; i++) {
        // 만들 수 없는 금액을 찾았을 때 반복 종료
        if (target < arr[i]) break;
        target += arr[i];
    }

    // 만들 수 없는 금액 출력
    cout << target << '\n';
}

 

  리뷰  

아이디어를 못 떠올림 ,, 저번에도 못 풀었는데 또 못풀다니 바보임