[백준 2246번] - 콘도 선정 / C++

www.acmicpc.net/problem/2246

2246번: 콘도 선정

문제

콘도를 선정할 때에는 가급적이면 싸고 바닷가에 가까운 곳으로 하려 한다. 이를 위해 우선 적당한 콘도 몇 곳을 후보로 선정하려 하는데, 다음 두 조건을 만족하는 콘도 X가 후보가 된다.

1. X보다 바닷가에 더 가까운 콘도들은 모두 X보다 숙박비가 더 비싸다.
2. X보다 숙박비가 더 싼 콘도들은 모두 X보다 바닷가에서 더 멀다.

각 콘도의 바닷가에서의 거리와 숙박비에 대한 정보가 주어졌을 때, 후보 콘도의 개수를 구해내는 프로그램을 작성하시오.

입력

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

출력

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

-------------------------------------------------------------------------------------------------------------------

풀이

<C++>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool Acending(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first) {
		return a.second < b.second;
	}
	return a.first < b.first;
}

int main() {
	int N;
	cin >> N;

	vector<pair<int, int>> condo;

	int D, C;

	for (int i = 0; i < N; ++i) {
		cin >> D >> C;
		condo.push_back({ D, C });
	}

	sort(condo.begin(), condo.end(), Acending);

	int answer = 1;
	int nowD = condo[0].first, nowC = condo[0].second;

	for (int i = 0; i < N - 1; ++i) {
		for (int j = i + 1; j < N; ++j) {
			if (condo[j].first > nowD && condo[j].second < nowC) {
				++answer;
				nowD = condo[j].first;
				nowC = condo[j].second;
				break;
			}
		}
	}

	cout << answer;

	return 0;
}

1번과 2번조건을 잘 생각해보면, 벡터에 넣은 콘도들의 거리와 가격들중 현재 D의 최솟값, C의 최댓값을 동시에 만족하는 값을 고정한 후, 인덱스를 늘려가며 현재 D보다 작은 거리, 현재 C보다 비싼 가격을 동시에 만족하는 값을 찾으며 서치를 하면 된다.

 

1. N을 입력받는다.

2. 콘도의 거리와 가격을 pair로 입력받는다.

3. nowD와 nowC가 동시에 조건문안의 조건을 만족할 경우, nowD와 nowC를 갱신하고 후보값을 늘린다.

4. 반복문이 모두 끝나면 answer를 출력한다.