[C++] 백준 20157번 : 화살을 쏘자!

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

20157번: 화살을 쏘자!

 

1. 완전탐색 문제이지만 탐색할 데이터를 어떻게 저장할지 고민해야하는 문제

기울기를 <x, y> 형태로 저장하고 map을 사용해 카운팅한다.

 

2. 괜히 2번생각해서

 

x와 y 구하기 전 x == 0 || y == 0이면 바로 map[make_pair(x, y)]++

 

조건을 넣었었는데 이 조건은 (0, 1) (0, 7)은 모두 (0, 1)로 저장되어야 하는 상황을 틀리게 만든다는 걸 채점 후에 알았다,,

#include <iostream>
#include <map>
#include <cmath>

using namespace std;

map<pair<int, int>, int> cnt;
int N, ans = 0, x, y;

int GCD(int num1, int num2) {
	while (num2 != 0) {
		int temp = num1 % num2;
		num1 = num2;
		num2 = temp;
	}

	return num1;
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);


	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;

		int gcd = GCD(abs(x), abs(y));
		cnt[make_pair(x / gcd, y / gcd)]++;
	}

	for (auto c : cnt) {
		ans = ans < c.second ? c.second : ans;
	}

	cout << ans;

	return 0;
}