[BOJ/백준] 25496 - 장신구 명장 임스

25496번: 장신구 명장 임스

---

피로도가 남아있다면 장신구 하나를 더 만들 수 있다

---

---

• 제목

장신구 명장 임스

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

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

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

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

---

• 입력

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

두 번째 줄에는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. (1 ≤ A_i ≤ 200)

 

---

• 출력

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

---

예제 입력1	예제 출력1
190 5 20 1 8 1 10	3

예제 입력2	예제 출력2
195 4 20 1 8 1	3

---

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define endl '\n'
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int fatigue, sz, *acc, cnt = 0;
    cin >> fatigue >> sz;
    acc = new int[sz];
    for(int n = 0 ; n < sz ; n++) cin >> acc[n];
    fatigue = 200 - fatigue;
	sort(acc, acc + sz);
    for(int n = 0 ; n < sz ; n++){
    	if(fatigue - acc[n] >= 0){
    		cnt++;
    		fatigue -= acc[n];
		}
		else break;
	}
	if(sz - cnt != 0 && fatigue > 0) cnt++;
	cout << cnt << endl;
    return 0;
}