[Python 3] BOJ 31864 눈송이 탕후루 만들기

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

오늘 해설할 문제는 눈송이 탕후루 만들기라는 문제이다.

먼저, 문제를 보았을 때, 제일 먼저 든 생각은 30만개의 눈송이와 30만개의 끝점들을 모두 brute force로 연산하면, 최소 30만의 제곱, 즉 900억개의 연산을 해야될 것으로 예상이 되었다. 이는 무조건적으로 시간 초과가 날 것임이 당연했다.

그래서, 먼저 시작점인 (0,0)과 눈송이 사이의 기울기를 통해, 기울기를 key로, 좌표의 x값을 value로 갖는 dictionary를 만들어서, 끝점을 보고 몇 개의 눈송이를 가지는지 확인할 때 (0,0)부터 끝점까지의 기울기와 같은 기울기를 가진 눈송이들만 확인하는 방식을 채택하였다.

하지만, 또 다른 문제점들이 있었다.

1. (3,4)와 (6,8)은 같은 기울기를 가지지만, 이를 저장할 때 기울기를 직접 나눠서 계산하면 부동소수점 오류가 날 수도 있다.
   • 기약분수꼴의 튜플을 이용하였다. 즉, 사전의 인덱스를 둘 다 d[(3,4)]에 저장하는 방식인 것이다.
   • 기약분수를 만들기 위해서 각각의 x,y 좌표를 x,y좌표의 gcd로 나눠서 기약분수를 연산한다.
2. (0,10)과 같은 좌표는 (0,0)와의 기울기가 존재하지 않는다. (좌표의 x값이 0이다.)
   • y축과 평행한 직선의 기울기가 나올 경우는 임의로 딕셔너리를 (1e10, 1e10)의 인덱스로 저장한다.

     but, dictionary의 value를 x값으로 저장한다고 하지 않았는가?

   • 해당 경우에만 좌표의 y값을 저장하였다.

이렇게 예외처리를 하였고, 모든 눈송이들의 좌표를 딕셔너리에 알맞게 저장한 후, 끝점들을 돌면서 이분탐색을 하여 몇 개의 꼬치들을 꽂을 수 있는지 설정하였다.

from collections import defaultdict
import sys
import math
input=sys.stdin.readline
n,m=map(int,input().split())
data=list(list(map(int,input().split())) for _ in range(n))
endpoints=list(list(map(int,input().split())) for _ in range(m))
d=defaultdict(list)
for i in range(n):
    x,y=data[i]
    if x==0:
        d[(int(1e10),int(1e10))].append(y)
    else:
        d[(x//math.gcd(x,y),y//math.gcd(x,y))].append(x)
answer=0
for i in d.keys():
    d[i].sort()
for i in range(m):
    x,y=endpoints[i]
    if x==0:
        cx=int(1e10)
        cy=int(1e10)
    else:
        cx,cy=x//math.gcd(x,y),y//math.gcd(x,y)
    if x==0:
        var=y
    else:
        var=x
    if d[(cx,cy)]:
        left=0
        right=len(d[(cx,cy)])-1
    else:
        continue
    temp=0
    while left<=right:
        mid=(left+right)//2
        if d[(cx,cy)][mid]>=0:
            right=mid-1
        else:
            left=mid+1
    if var>0:
        temp=left
    else:
        temp=right
    left=0
    right=len(d[(cx,cy)])-1
    if var>0:
        while left<=right: 
            mid=(left+right)//2
            if d[(cx,cy)][mid]<=var:
                left=mid+1
            else:
                right=mid-1
        temp=right-temp+1
    else:
        while left<=right:
            mid=(left+right)//2
            if var<=d[(cx,cy)][mid]:
                right=mid-1
            else:
                left=mid+1
        temp=temp-left+1
    answer=max(answer,temp)
print(answer)

var은 찾고자 하는 x값 (x==0인 경우 y값)이다.
먼저 1차 이분탐색으로 (0,0)의 좌표일 때의 눈송이의 인덱스를 찾고,
이후 2차 이분탐색으로 (var,0) (x==0인 경우 (0,var))의 인덱스를 찾아서 연산하였다.
여기서 두 가지의 이분탐색을 사용하는데,
var가 0보다 큰 경우면 눈송이들 중 0보다 큰 눈송이를 찾아야하기에 left의 값을 저장,
var가 0보다 작은 경우면 눈송이들 중 0보다 작은 눈송이를 찾아야하기에 right의 값을 저장하였다.

var을 찾을 때도 x좌표가 양수인 경우, 음수인 경우로 나누어서, off-by-one으로 이분탐색이 틀리지 않도록 연산하였다.