[BOJ] 백준 20157 화살을 쏘자! (JAVA)

[BOJ] 백준 20157 화살을 쏘자! (JAVA)Algorithm/- Baekjoon2024. 7. 7. 15:11@Koben

Table of Contents

📑 문제

좌표 (0,0)과 (x, y)의 기울기를 구하고, 기울기가 같은 풍선을 세어보자

풍선의 개수는 N <= 100,000개 풍선의 좌표는 -1,000,000 <= x, y <= 1,000,000... 매우 크다

대충 봐도 모든 좌표를 탐색하는 건 불가능해 보인다

문제에서는 0,0에서 화살을 날려 -> (x, y) 풍선을 맞춰 터트릴 수 있다고 한다. 최대한 많은 풍선을 터트리려면 어떻게 해야 할까?

0,0 -> 1,2로 화살을 쐈다면 자연스럽게 화살의 이동 방향에 존재하는 풍선들은 터질 것이다. 이것을 그림으로 그려보면 위 처럼 된다.

즉 풍선 A -> 풍선 B를 잇는 직선의 기울기를 구하고, 같은 기울기에 속한 풍선의 개수를 세면 된다!

기울기 M을 구하는 공식은 M = (y2-y1) /( x2-x1)이다, 그 후 기약분수로 표현하기 위해 최대공약수 도 구해서 나눠주면 된다

최대공약수는 절댓값 형태로 나타내야 한다, 화살은 내 앞으로만 나아가기 때문에 다른 분면을 포함하면 안 된다

백준을 풀면서 가장 편식했던 문제유형 중 하나이다... 기하학 편식을 멈춰주세요ㅠㅠ