코드 포스(Code Force) 390 - A. Inna and Alarm Clock

문제 유형: 구현

문제 URL: https://codeforces.com/contest/390/problem/A

  이 문제는 대표적인 단순 구현 문제입니다. 이 문제는 초기에 101 X 101 이차원 격자에 여러 개의 알람 시계가 있다고 가정합니다. 이 때 가로 혹은 세로에 있는 알람을 모두 한 번에 끌 수 있다고 합니다. 가로 혹은 세로 라인을 선택하는 최소 횟수를 구하면 됩니다.

  다만 알람을 끌 때 모두 가로로 끄거나, 모두 세로로 끄거나 둘 중 하나만 선택해야 합니다. 예를 들어 2번 가로 줄의 알람을 모두 끄고, 3번 세로 줄의 알람을 모두 끄는 것은 안 됩니다. 여러 번 알람을 끌 때 항상 가로로만 끄거나 세로로만 꺼야 한다는 겁니다. 사실 이러한 조건 때문에 이 문제는 매우 쉬운 단순 구현 문제에요.

  만약에 가로, 세로를 번갈아가면서 선택하며 끌 수 있었다면 이분 매칭(Bipartite Matching) 문제로 분류되어 조금 더 어려워집니다. 하지만 이 문제는 반드시 가로 혹은 세로로만 꺼야 한다는 강력한 제약 조건이 붙어 있으므로 단순히 <가로로만 끌 때의 경우의 수>와 <세로로만 끌 때의 경우의 수> 중에서 더 작은 수를 계산하여 출력하기만 하면 됩니다.

※ 예시 입출력 ※

input

4
1 1
1 2
2 3
3 3

output

3

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <stdio.h>
#include <limits.h>

using namespace std;

int a[101][101];

int main(void) {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
	}
	int res = INT_MAX;
	int count = 0;
	for(int i = 0; i < 101; i++) {
		for(int j = 0; j < 101; j++) {
			if(a[i][j]) {
				count++;
				break;
			}
		}
	}
	res = min(res, count);
	count = 0;
	for(int i = 0; i < 101; i++) {
		for(int j = 0; j < 101; j++) {
			if(a[j][i]) {
				count++;
				break;
			}
		}
	}
	res = min(res, count);
	cout << res;
	return 0;
}