[BOJ/Silver 5] 백준 25496 장신구 명장 임스(C++)

문제 링크

https://www.acmicpc.net/problem/25496

25496번: 장신구 명장 임스

 

문제

메이플스토리에는 전문 기술이라는 제작 시스템이 있다. 전문 기술은 특정량의 피로도가 쌓이는 대신 다양한 장비 및 비약을 제작할 수 있는 시스템이다. 장신구 명장인 임스는 어떻게 하면 더 효율적으로 많은 장신구를 제작할 수 있을지 고민에 빠졌다.

임스가 만들 수 있는 장신구는 N개가 있고, 각각의 장신구를 만들면 Ai만큼의 피로도가 누적된다.

피로도가 200 미만인 경우, 장신구를 제작할 수 있다. 현재 쌓인 피로도가 P일 때, 임스가 제작할 수 있는 장신구의 최대 개수를 구해보자!

 

입력

첫 번째 줄에 정수 P와 정수 N이 공백으로 구분되어 주어진다. (1 ≤ P ≤ 200, 1 ≤ N ≤ 1,000)

두 번째 줄에는 정수 A1, A2, …, AN이 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ 200)

 

출력

제작할 수 있는 장신구의 최대 개수를 출력하시오.

 

예제 입력 1

190 5
20 1 8 1 10

예제 출력 1

3

예제 입력 2

195 4
20 1 8 1

예제 출력 2

3

 

두 번째 장신구와 네 번째 장신구를 만들고 나면 피로도는 197이 된다.

피로도가 200 미만이므로 첫 번째 장신구나 세 번째 장신구 중 하나를 더 제작할 수 있고, 따라서 만들 수 있는 최대 장신구의 개수는 세 개가 된다.

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

최대한 많은 장신구를 제작해야 하므로, 피로도가 적은 순으로 장신구를 오름차순 정렬한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int P, N;
vector<int> A;
int Answer;

void input() {
    cin >> P >> N;
    A.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
}

void settings() {
    sort(A.begin(), A.end());
    for (int i = 0; i < N; i++) {
        if (P >= 200) {
            break;
        }
        P += A[i];
        Answer++;
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}