취미로 코딩하기

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

이번에 볼 문제는 백준 6032번 문제인 Toy Shopping이다.
문제는 아래 링크를 확인하자.

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

두 (Ji, Pi)의 쌍 (A,B), (X,Y)에 대하여, A/B와 X/Y의 크기를 정수연산으로 비교할 수 있는 연산 A*Y > B*X 을 이용하여 실수오차 없이 문제를 해결하자.

위의 비교연산을 이용해 배열을 정렬하고 문제를 풀 수도 있다.

찾아야 하는 쌍의 개수가 셋 뿐이므로, 굳이 정렬을 하지 않고 최선인 값을 세개만 관리해가는 방식의 알고리즘을 하드코딩해도 좋다.

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

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

int N;
pair<pair<ll, ll>, int> arr[25000];

bool comp(pair<pair<ll, ll>, int> x, pair<pair<ll, ll>, int> y) {
	return x.first.first * y.first.second > x.first.second * y.first.first;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		ll x, y; cin >> x >> y;
		arr[i] = make_pair(make_pair(x, y), i + 1);
	}

	sort(arr, arr + N, comp);

	cout << arr[0].first.second + arr[1].first.second + arr[2].first.second << '\n';
	for (int i = 0; i < 3; i++) cout << arr[i].second << '\n';
}