[백준-파이썬] 20157: 화살을 쏘자!

문제로 가기!

인사

요즘 싸피 pjt를 하다가 오랜만에 문제 푸니 좋다~
꾸준히 풀어야 하는데...!!

설명

처음에는 모든 각도를 계산해야 하나..? 어떻게 계산하지..? 하다가, 기울기를 구하면 된다는 걸 알았다.
그런데 딱 나누어서 떨어지지 않는 것(무한 소수 -> 10/3 = 3.33333333333......)이 문제가 된다고 한다.
이 블로그를 보고 알았다 !!

그래서 x, y를 최대한 약분한 것을(0,0에서 시작하므로) 튜플에 넣어서, 기울기로 봐줘야 한다.
딕셔너리(역시 default dictionary가 너무 편하다 >< )에 그 기울기를 key로 삼아서, 그 기울기를 만날 때마다 1씩 더했다.

나중에 딕셔너리.value()를 이용해서, 값들을 봐주면서 제일 큰 값을 정답으로 출력했다.

헷갈렸던 부분

처음에 x, y를 최대한 약분할 때, 부끄럽지만 이런 식으로 했다... (변명을 하자면, 예제에 있는 것들은 잘 돼서... 8, 16 -> 1,2 | 2, 4 -> 1, 2)
계속 16 % 에서 틀렸다... (10, 4 -> 5, 2가 안됨.;;)

        while x % y == 0 and y != 1:  # 가능할 때까지 약분하기(y가 더 클 때)
            x //= y
            y //= y

        while y % x == 0 and x != 1:  # 가능할 때까지 약분하기(x가 더 클 때)
            y //= x
            x //= x

유클리드 호제법으로 x, y의 최대공약수를 구한 후에 x, y를 이 값으로 나눈 몫을 구해야 한다.

코드

import sys
import collections

input = sys.stdin.readline

slope = collections.defaultdict(int)

N = int(input())
balloons = list(tuple(map(int, input().split())) for _ in range(N))

def find_gcd(a,b): # 유클리드 호제법

    while b != 0:
        r = a % b
        a,b = b, r

    return abs(a)

# 기울기 구하기
for x, y in balloons:
    if x == 0 and y == 0:  # 0, 0에는 풍선 둘 수 없음
        continue
    elif x == 0:  # x축만 0이면
        # 방향 두개로 나뉨
        if y < 0:
            slope[(0, -1)] += 1
        else:
            slope[(0, 1)] += 1

    elif y == 0:  # y축만 0이면
        # 방향 두 개로 나뉨
        if x < 0:
            slope[(-1, 0)] += 1
        else:
            slope[(1, 0)] += 1

    else:
        gcd = find_gcd(x, y)
        x //= gcd
        y //= gcd
        slope[(x, y)] += 1

# 젤 풍선 많이 터뜨릴 수 있는 방향일 때, 그 점수 구하기
ans = 0
for value in slope.values():
    ans = max(ans, value)

print(ans)