취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14012번 문제인 Large PhD Restaurant이다.
문제는 아래 링크를 확인하자.

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

문제를 읽으면 이득이 되는 도전을 최대한 많이 해야 할 것 같다는 느낌이 온다.

돈을 잃는 도전은 후보에서 제외하면, 어떤 도전을 할 수 있다면 그보다 도전비용이 적은 도전들은 전부 하는 것이 항상 최선이 됨을 알 수 있다. 따라서 도전비용이 적은 도전서부터 하나하나 해나가 도전이 불가능할 때까지 도전하는 것이 항상 최선의 전략이 된다.

답을 32비트 정수 자료형으로 담을 수 없을 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

ll arr[100001];

vector<pair<ll, ll>> vec;


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

	int N; ll M; cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < N; i++) {
		ll x; cin >> x;
		if (arr[i] < x) vec.emplace_back(make_pair(arr[i], x - arr[i]));
	}

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

	for (auto p : vec) {
		if (p.first <= M) M += p.second;
	}

	cout << M;
}