백준] 2246 - 콘도 선정(ACM-ICPC Regionals)

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 콘도의 개수를 나타내는 자연수 N(1≤N≤10,000)이 주어진다. 다음 N개의 줄에는 각 콘도에 대한 정보를 나타내는 두 정수 D(1≤D≤10,000), C(1≤C≤10,000)가 주어진다. D는 그 콘도의 바닷가로부터의 거리를 나타내고, C는 그 콘도의 숙박비를 나타낸다. D와 C값이 서로 같은 콘도가 주어지지는 않는다.

출력

첫째 줄에 후보가 될 수 있는 콘도의 수를 출력한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	int n, cnt = 0;
	bool check;
	cin >> n;
	vector<pair<int, int> > arr(n);

	for (int i = 0; i < n; i++)
		cin >> arr[i].first >> arr[i].second;

	for (int i = 0; i < n; i++)
	{
		check = false;
		for (int j = 0; j < n; j++)
		{
			if (i != j)
			{
				if (arr[i].first > arr[j].first)
				{
					if (arr[i].second >= arr[j].second)
					{
						check = true;
						break;
					}
				}
				else if (arr[i].second > arr[j].second)
				{
					if (arr[i].first >= arr[j].first)
					{
						check = true;
						break;
					}
				}
			}
		}
		if (!check)
			cnt++;
	}

	cout << cnt;
}

Tip

문제에 제시된 조건에 맞춰서 모든 경우를 조사하면 된다. 비교 대상과 거리가 가까우면서도 비용이 더 들어가거나, 비용이 많이 들어가면서도 거리가 먼 경우가 발견되면 해당 콘도는 후보군에서 제외하면 된다.