취미로 코딩하기

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

이번에 볼 문제는 백준 24145번 문제인 折り紙 (Origami)이다.
문제는 아래 링크를 확인하자.

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

주어진 조건을 잘 확인하면, 각 종이가 덮는 칸은 400개 이하이므로 각 종이로 덮인 칸의 수의 합은 100만개 이하임을 알 수 있다.

이를 이용하면, 종이로 덮인 각 칸에 대하여 그 칸이 덮인 횟수를 map을 이용해 세어 문제를 해결할 수 있음을 알 수 있다. 이를 구현하여 문제를 해결하자.

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

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int N, X, Y;;
map<pair<int, int>, int> mp;
int mx, cnt;

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

	cin >> N >> X >> Y;
	while (N--) {
		int X1, Y1, X2, Y2; cin >> X1 >> Y1 >> X2 >> Y2;
		for (int x = X1; x <= X2; x++) {
			for (int y = Y1; y <= Y2; y++) {
				mp[make_pair(x, y)]++;
			}
		}
	}
	for (auto &p : mp) {
		if (mx < p.second) mx = p.second, cnt = 1;
		else if (mx == p.second) cnt++;
	}

	cout << mx << '\n' << cnt;
}