백준 20157 화살을 쏘자! (Python,Pypy)

문제는 이렇게 주어졌습니다.

즉, 원점을 통과하는 직선이 주어진 points을 얼마나 많이 통과하는가? 에 대한 내용이 되겠습니다.

import sys
input = sys.stdin.readline

N = int(input())
dict = {}
A = []
for i in range (0,N):
    a,b = map(int,input().split())
    c = math.gcd(a,b)
    a //= c
    b //= c
    if (a,b) not in dict:
        dict[(a,b)] = 1
    else:
        dict[(a,b)] += 1


print(max(dict.values()))

해설)

제가 작성한 코드 위와 같습니다.
사용한 아이디어는 Projection (사영) 입니다.

예를 들어보겠습니다.
(100,200) 라는 점이 주어져있을 때, x좌표와 y좌표의 최대공약수는 100입니다.
두 좌표를 최대공약수로 나눠주면 새로운 좌표는 (1,2)가 되겠습니다.

이렇게 얻어진 (1,2)라는 새로운 좌표는 x좌표와 y좌표가 서로소임을 알 수 있습니다.
같은 방법으로, (1024,2048)이라는 점이 주어졌다면
최대공약수 1024로 x,y좌표를 나누어 새로운 좌표 (1,2)를 얻습니다.

이제 이것들을 딕셔너리에 넣어주겠습니다.
만약 (1,2)라는 새로운 좌표가 딕셔너리 안에 존재하고있다면,
그것의 value 값을 하나 늘려주고,
만약 딕셔너리 안에 없다면, 새로운 key (1,2) - value = 1를 추가해주면 되겠습니다.

그리고 키 값 중 최대치를 출력해주면 되겠습니다.