백준[ 13423 | Python ] Three Dots

문제

https://www.acmicpc.net/problem/13423

풀이

먼저 점 a를 잡아주고 그 뒤에 임의의 점 b를 잡는다.
그 둘 사이의 거리만큼 다른 점 하나가 필요하기 때문에 아직 정해지지 않은 점 c에 그 거리만큼 더해주어
점 a와 점 b사이의 거리 만큼 떨어진 점을 이분탐색으로 찾아주면 되는 문제였다.
문제에서 점은 일직선 상에 놓여있는 것으로 설명되지만
실제로 주어지는 입력은 정렬되어 있지 않기 때문에 정렬을 먼저 해주어야 한다.

추가로 pypy제출이 마음편하다. 제출 후에 다른 분들의 코드를 봤는데, 근래 2년 가까이는 python으로 통과한 이력이 없었다.

import sys
input = sys.stdin.readline

def bin_search(l,r,t):
    while l<=r:
        m = (l+r)//2
        if dots[m] == t:
            return 1
        if dots[m] > t:
            r = m-1
        else:
            l = m+1
    return 0

for _ in range(int(input().rstrip())):
    case = 0
    n = int(input().rstrip())
    dots = sorted(list(map(int, input().split())))
    l, r = 0, n-1
    
    for i in range(n-1):#점 a
        for j in range(i+1, n): #점 b
            dist = abs(dots[j]-dots[i])# 두 점 사이의 거리
            if bin_search(l, r, dots[j] + dist):#target은 두점사이 거리만큼 떨어진 다른 점
                case+=1
    print(case)

생각 & 정리

이 전까지는 탐색할 대상이 하나 뿐이라서 그렇게 깊은 고민 없이도 파악 가능한 문제였는데,
임의의 점 두개를 미리 잡아주고 그 사이 거리만큼 따로 떨어진 점을 target으로 두고 찾으면 되겠다는 생각이 쉽사리 떠오르지 않았다.
꽤 오랜시간 고민하다가 다른 분의 블로그를 참고했는데 같은 거리의 점을 찾는 법이 떠올리지 못한 방법이라서 놀라웠다.
언제쯤 한 문제를 다방면으로 생각할 수 있을지 고민이다.

참고

https://fieldanimal.tistory.com/42