๋ฐ์ํ
https://softeer.ai/practice/6288
๋ฌธ์ ์ค๋ช
์ฒซ ๋ฒ์งธ ์ค์ ๋ฐฐ๋ญ์ ๋ฌด๊ฒ W์ ๊ท๊ธ์์ ์ข ๋ฅ N
i๋ฒ์งธ ๊ธ์์ ๋ฌด๊ฒ Mi์ ๋ฌด๊ฒ๋น ๊ฐ๊ฒฉ Pi๊ฐ ์ฃผ์ด์ง๋ฉด
๋ฐฐ๋ญ์ ๋ด์ ์ ์๋ ๊ฐ์ฅ ๋น์ผ ๊ฐ๊ฒฉ์ ์ถ๋ ฅํ๋ ๋ฌธ์
ํน์ดํ๊ฒ ์ ๋ํฑ ๊ธฐ๋ฅ ๋๋ฌธ์ ๊ท๊ธ์์ ์๋ผ์ ์๋ ค์ง ๋ถ๋ถ์ ๋ฌด๊ฒ๋งํผ ๊ฐ์น๋ฅผ ๊ฐ์ง ์ ์๋ค
ํ์ด
์ฃผ์ด์ง ๋ณด์์ ๊ฐ์น๊ฐ ๋์ ์์๋๋ก ์ ๋ ฌํ ๋ค
๊ฐ์น๊ฐ ๋์ ๋ณด์๋ถํฐ ์ฐจ๋ก๋ก ๊ฐ๋ฐฉ์ ๋ฃ์ผ๋ฉฐ ๊ฐ์น๋ฅผ ๊ณ์ฐํ๋ค
๊ฐ๋ฐฉ ๋จ์ ์์ด ๋ถ์กฑํ๋ฉด ๊ทธ๋งํผ ๋ณด์์ ์๋ผ ๋ฃ์.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> ci;
bool cmp(ci a, ci b) {
return a.second > b.second;
}
int main() {
int w, n;
cin >> w >> n;
vector<ci> jewel(n);
for(int i=0; i<n; i++) {
int m, p;
cin >> m >> p;
jewel[i] = {m,p};
}
sort(jewel.begin(), jewel.end(), cmp);
int ans = 0;
for(int i=0; i<n; i++) {
int m = jewel[i].first;
int p = jewel[i].second;
if(w>m) {
ans += m*p;
w -= m;
} else {
ans += w*p;
break;
}
}
cout << ans;
return 0;
}
๋ฐ์ํ