[BOJ/C++] 23559번: 밥

문제

풀이

코너 A를 몇 번 방문해도 되는지 수식으로 구한 후, A - B가 큰 값부터 해당 개수만큼 차례대로 선택하면 된다. A - B가 음수일 때는 B를 선택함에 유념한다. 필자는 A - B에 대한 배열을 추가적으로 구현하여, 해당 배열을 정렬 후 일정 금액 초과는 반드시 선택, 일정 금액은 남은 선택 개수만큼 선택하는 방식으로 구현하였다.

 

코드

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int n, x;
cin >> n >> x;

int cnt = (x - 1000 * n) / 4000;
int arr[100000][2];
int diff[100000];

for (int i = 0; i < n; i++) {
cin >> arr[i][0] >> arr[i][1];
diff[i] = arr[i][0] - arr[i][1];
}
sort(diff, diff + n);
int difff;
if (cnt == 0) difff = 30000;
else difff = diff[n - cnt];

if (difff < 0) difff = 0;

int flavor = 0;
for (int i = 0; i < n; i++) {
if (arr[i][0] - arr[i][1] > difff && cnt > 0) {
cnt--;
flavor += arr[i][0];
}
else flavor += arr[i][1];
}
flavor += cnt * difff;

cout << flavor;

}