[BOJ][🟡5][백준#22238] 가희와 btd5

문제 출처

BAEKJOON Online Judge #22238

문제

btd5에는 Darting Gun Tower가 있습니다. Darting Gun Tower는 아래의 알고리즘으로 풍선을 공격합니다.

공격하고자 하는 목표물의 방향으로 공격 방향을 바꿉니다. 공격 방향에 있는 풍선들의 체력을 d씩 낮춥니다.

Darting Gun Tower는 좌표 (0, 0)에 하나 있습니다. Darting Gun Tower가 공격을 하게 되면, 공격하는 방향에 놓인 모든 풍선들은 동일한 수치의 피해를 입히게 됩니다. 초기에 풍선은 N개 있고, Darting Gun Tower는 공격을 M번 하였습니다. 공격을 끝낼 때 마다, 남은 풍선의 수를 세어 주세요. 초기 상태에 Darting Gun Tower가 특정 방향으로 데미지가 109 이상의 공격을 했을 때, 모든 풍선을 제거할 수 있는 방법이 존재합니다.

입력

첫 번째 줄에 N, M이 주어집니다. 2번째 줄부터 N+1번째 줄까지 풍선이 있는 x좌표, y좌표, 체력이 주어집니다. N+2번째 줄부터 N+M+1번째 줄까지 Darting Gun Tower의 공격 방향 (x, y)와, Darting Gun Tower가 준 데미지 d가 주어집니다.

출력

x번째 줄에 x번째 공격이 끝났을 때 남은 풍선의 개수를 출력해 주세요.

제한

N과 M은 구간 [1, 2×105]에 속하는 정수입니다. 풍선들의 x 좌표와 y 좌표는 [-109, 109]에 속하는 정수입니다. 풍선들의 위치는 고정되어 있으며, 풍선이 있는 위치에 Darting Gun Tower가 있지 않습니다. 두 개 이상의 풍선이 같은 위치에 있지 않습니다. 풍선들의 hp와 Darting Gun Tower가 주는 데미지는 구간 [1, 109]에 속하는 정수입니다.

예제

입력

3 1
1 1 3
3 3 4
2 2 2
1 1 3

출력

1

My Sol

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
from math import gcd

def find_s(x, y):
    g = gcd(x, y)
    return (x/g, y/g)


N, M = map(int, input().split())
D = {}
for _ in range(N):
    x, y, d = map(int, input().split())
    s = find_s(x, y)
    if not D.get(s, ''):
        D[s] = [0, []]
    heappush(D[s][1], d)

for _ in range(M):
    x, y, d = map(int, input().split())
    s = find_s(x, y)
    if not D.get(s, ''):
        print(N)
        continue
    D[s][0] += d
    while D[s][1]:
        if D[s][1][0] > D[s][0]: break
        heappop(D[s][1])
        N -= 1

    print(N)

꽤나 까다로운 문제였다. heap을 사용해서 조금 어렵게 풀었던 것도 같지만 풀 때에는 최선이었다…

1. 딕셔너리 D는 특정 slope에서의 누적 데미지와 해당 slope의 영향권에 있는 풍선들의 체력들을 저장한다.
2. M번의 공격 입력동안 데미지를 해당 slope의 누적 데미지에 더하고 이보다 작거나 같은 체력의 풍선들은 제거하며 N을 줄인다.
3. slope는 y/x로 구하려 했으나 극단적인 케이스에서 매우 작은 소수의 크기 차이는 구분이 되지 않으므로 최대공약수 gcd를 활용해 구분한다.

최초엔, 같은 라인에 있는 구분을 y/x의 기울기 계산을 통해서 했는데, 알 수 없는 오류가 발생했다. 하지만 극단적인 사계를 활용해 문제를 파악할 수 있었다.

1 2
999999998 1000000000 10
999999998 999999999 20
999999997 999999998 30

이 경우 1.0000…1, 2 수준으로 매우 작은 크기의 차이가 발생하고, 이는 프로그래밍의 소수 처리 특성상 같은 수로 처리된다. 하지만 그러면 안 되므로 최대공약수를 활용한 구분을 해주었다.

또한 gcd 도입 전에 방향을 확인하기 위해 12시 방향부터 시계방향으로 1부터 8까지의 구분을 두어 return했다.

def find_s(x, y):
    g = gcd(x, y)
    if not x: return (0, 0, 1) if y > 0 else (0, 0, 5)
    if not y: return (0, 0, 3) if x > 0 else (0, 0, 7)

    if x > 0: d = 2 if y > 0 else 4
    else: d = 8 if y > 0 else 6

    return (x/g, y/g, d)

하지만 최대공약수를 사용하면 방향의 파악이 불필요하므로 아래과 같이 짧게 표현될 수 있다.

def find_s(x, y):
    g = gcd(x, y)
    return (x/g, y/g)

그런데 의외로 위의 함수가 연산시간이 더 짧았다. 분기처리가 많아서 당연히 더 오래 걸릴 줄 알았는데, gcd 함수를 덜 사용하기 때문이 아닐까 추측해본다.

결과

맞았습니다!!