알고리즘/BOJ
[BOJ 20157, Python 3] 화살을 쏘자!
70825
2021. 10. 4. 13:54
반응형
https://www.acmicpc.net/problem/20157
20157번: 화살을 쏘자!
호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는
www.acmicpc.net
풀이
좌표평면에서 한 방향으로 화살을 쏜다는 것은 기울기가 설정되어 있다는 뜻입니다.
그래서 제 1사분면부터 제 4사분면까지 defaultdict를 만들어주고, 각 좌표의 최대공약수를 통해 기울기를 구해주고 조건에 맞는 사분면에 넣어주면 됩니다.
x = 0 혹은 y = 0일 때는 따로 변수를 둬서 구해주고, 여기에 있는 값들중 최댓값을 구해주면 됩니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from math import gcd
from collections import defaultdict as dfd
input = __import__('sys').stdin.readline
one = dfd(lambda : 0)
two = dfd(lambda : 0)
three = dfd(lambda : 0)
four = dfd(lambda : 0)
plus_x, minus_x, plus_y, minus_y = 0, 0, 0, 0
n = int(input())
for i in range(n):
x, y = map(int, input().split())
if x == 0:
if y > 0: plus_y += 1
else: minus_y += 1
continue
if y == 0:
if x > 0: plus_x += 1
else: minus_x += 1
continue
vx, vy = abs(x), abs(y)
g = gcd(vx, vy)
nx, ny = vx // g, vy // g
if x > 0 and y > 0: one[str(nx)+'/'+str(ny)] += 1
if x < 0 and y > 0: two[str(nx)+'/'+str(ny)] += 1
if x < 0 and y < 0: three[str(nx)+'/'+str(ny)] += 1
if x > 0 and y < 0: four[str(nx)+'/'+str(ny)] += 1
ans = 0
if len(one.values()) > 0: ans = max(ans, max(one.values()))
if len(two.values()) > 0: ans = max(ans, max(two.values()))
if len(three.values()) > 0: ans = max(ans, max(three.values()))
if len(four.values()) > 0: ans = max(ans, max(four.values()))
print(max(ans, plus_x, minus_x, plus_y, minus_y))
|
cs |
반응형