[BOJ/Platinum 4] 백준 23035 가톨릭대는 고양이를 사랑해(C++)

문제 링크

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

 

문제

가톨릭대학교에는 많은 고양이가 있다. 고양이를 사랑하는 많은 학생 중 한 명인 쿠기는 수업 시간보다 항상 일찍 등교해서 고양이 밥을 챙겨주곤 했다. 안타깝게도 이제 4학년이 된 쿠기는 취업 준비에 바빠 고양이를 챙기는 것에 많은 시간을 쏟을 수 없게 되었다.

그런데도 고양이를 사랑하는 쿠기는 학교 정문에서부터 수업이 있는 다솔관까지 가는 여러 경로 중에, 가장 많은 고양이를 만나 밥을 챙겨 줄 수 있는 경로를 찾고 싶어 한다. 쿠기는 다솔관까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동하는 시간은 1만큼 걸린다. 이때, 고양이에게 밥을 주는 시간은 무시할 수 있을 정도로 짧다. 쿠기는 정문에서 다솔관까지 가장 빠르게 움직일 때만 수업에 늦지 않을 수 있다. 마음 착한 쿠기가 수업에 늦지 않으면서 최대한 많은 고양이의 밥을 챙길 수 있도록 도와주자.

 

 

가톨릭대는 크기가 N × M인 직사각형이고, 정문은 (0, 0), 다솔관은 (N, M)에 있다.

 

입력

첫 번째 줄에 정수 N, M(0 ≤ N, M ≤ 1,000,000,000)이 주어진다.

두 번째 줄에 고양이의 수를 나타내는 정수 T(0 ≤ T ≤ 100,000)가 주어진다.

세 번째 줄부터 T개의 줄에 고양이의 위치를 나타내는 정수 r, c(0 ≤ r, c ≤ 1,000,000,000)가 주어진다. 두 개 이상의 좌표가 중복되는 경우는 없고, 가톨릭대 밖에 고양이가 존재할 수 있다.

 

출력

첫 번째 줄에 수업 시간 전에 밥을 챙겨줄 수 있는 고양이의 최대 마릿수를 출력한다.

 

예제 입력 1

5 6
6
0 0
1 6
2 2
2 1
4 3
5 6

예제 출력 1

5

예제 입력 2

100 100
3
101 101
102 100
100 100

예제 출력 2

1

 

알고리즘 분류

• 정렬
• 다이나믹 프로그래밍
• 이분 탐색

 

풀이

먼저 최소의 이동으로 최대한 많은 고양이에게 밥을 줘야 하므로, 다솔관까지 이동하면서 반드시 오른쪽이나 아래쪽 방향으로만 이동할 수밖에 없다. 따라서, 고양이가 위치한 모든 좌표를 X좌표를 기준으로 오름차순 정렬한다. X좌표가 동일하다면, Y좌표를 기준으로 오름차순 정렬한다.

X좌표를 기준으로 고양이들의 위치를 정렬했으므로 X좌표가 기준이 되어 Y좌표에 대한 중복 가능한 LIS를 구해야 한다.

중복을 허용해야 하므로, lower_bound 대신 upper_bound를 이용한다. 이렇게 되면, 현재 Y좌표보다 큰 값 중 가장 작은 값의 인덱스를 구하는 것이 되므로, 그 인덱스를 구하지 못 했다면 현재 Y좌표를 새로이 LIS에 추가하는 것이 되므로 중복이 허용된다.

밥을 줘야 할 고양이의 최대 마릿수를 찾기만 하면 되기 때문에 굳이 고양이의 위치를 저장할 필요는 없고 DP 배열에 LIS에 포함될 수 있는 Y좌표만을 구하고, 마지막에 DP 배열의 크기를 반환하면 된다.

LIS를 이 정도까지 응용할 수 있는 것에 감동을 받았고, 관련 문제를 더 풀며 공부를 해야겠다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, T;
vector<pair<int, int> > Cats;
vector<int> Numbers;
int Answer;

void input() {
	cin >> N >> M;
	cin >> T;
	Cats.resize(T);
	for (int i = 0; i < T; i++) {
		cin >> Cats[i].first >> Cats[i].second;
	}
}

int findCats() {
	int Result = 0;
	vector<int> DP;

	for (int i = 0; i < T; i++) {
		if ((Cats[i].first > N) || (Cats[i].second > M)) {
			continue;
		}
		auto IT = upper_bound(DP.begin(), DP.end(), Cats[i].second);
		int Index = IT - DP.begin();

		if (IT == DP.end()) {
			DP.push_back(Cats[i].second);
		}
		else {
			*IT = Cats[i].second;
		}
	}

	Result = (int)DP.size();

	return Result;
}

bool comp(pair<int, int> A, pair<int, int> B) {
	if (A.first == B.first) {
		return (A.second < B.second);
	}

	return (A.first < B.first);
}

void settings() {
	sort(Cats.begin(), Cats.end(), comp);
	Answer = findCats();
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
    FASTIO

	input();
	settings();
    printAnswer();

    return 0;
}