| 시간 제한 | 메모리 제한 |
| 2초 | 1024MB |
문제
2차원 좌표 평면상에 현빈이와 수연이가 살고 있다. 현빈이와 수연이는 통화를 자주 하는데, 둘 다 오래된 핸드폰을 쓰기 때문에 통화가 자주 끊긴다. 둘은 이리저리 자리를 옮기며 통화하던 중, 둘의 위치를 잇는 직선의 기울기가 K라면 통화가 끊기지 않는다는 사실을 발견했다.
현빈이와 수연이가 있을 수 있는 N개의 2차원 좌표가 주어질 때, 통화가 끊기지 않도록 현빈이와 수연이를 배치하는 경우의 수를 구해주자.
입력
첫째 줄에는 N과 K가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 200,000; -10^9 ≤ K ≤10^9)
둘째 줄부터 N개 줄에 걸쳐 i번 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다. (-10^9 ≤ xi, yi ≤ 10^9)
같은 좌표는 두 번 이상 입력되지 않으며, 입력으로 주어지는 모든 값은 정수다.
출력
통화가 끊기지 않도록 현빈이와 수연이를 배치하는 경우의 수를 구하여 출력하시오.
풀이
N의 범위가 200,000까지로 어떤 점 i에 대해 나머지 점들과의 기울기를 직접 계산하는 방법으로 문제를 해결하면 O(N^2)으로 시간 내에 해결할 수 없다.
좌표평면에서 두 지점을 잇는 직선의 기울기가 K이기만 하면 된다는 것이 문제 해결의 핵심인데, 어떤 직선 y = K*x + b가 있다고 해보자. 어떤 점이든 이 직선의 방정식에 K값과 함께 x, y좌표를 각각 대입해주면 y절편인 b의 값을 특정할 수 있다. 어떤 점의 y절편이 같다면 두 점은 기울기가 K인 직선상에 함께 있을 수 있는 것이다.
따라서 문제는 y - K * x식에 x, y좌표를 각각 대입해 얻은 y절편이 각각 몇 회 나타나는지 확인하는 문제로 변환된다. 만약 y절편이 5인 점이 4개 있었다면 이 4개의 점 중 2개를 순서 없이 고르는 경우의 수를 6개라고 구할 수 있다. 이런 식으로 모든 입력에 대해 y절편 값의 수를 dictionary로 관리한다. 마지막에는 모든 key의 value를 확인해 2 이상인 경우에만 조합의 수를 구해 누적한다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
N, K = map(int, input().split())
y_inter = set()
count = dict()
for _ in range(N):
x, y = map(int, input().split())
k = y - x * K
if k in y_inter:
count[k] += 1
else:
count[k] = 0
y_inter.add(k)
res = 0
for k in list(y_inter):
if count[k]:
res += count[k] * (count[k] + 1)
print(res)
solution()
