[백준-파이썬] 22942: 데이터 체커

문제 보러 가기!

처음 아이디어

원의 중심 좌표 x 기준으로 정렬
옆에 있는 두 개 원씩 만나는지 보기 라는 아이디어로 짠 코드

두 개 원이 만나는지는 '힌트'에 있는 수학 공식을 참고했다 !

코드

import sys

input = sys.stdin.readline

def is_meet(circle1, circle2):
    x1, r1 = circle1
    x2, r2 = circle2
    if (x1 - x2) == 0 and r1 != r2: # 동심원
        return False

    if (r1 - r2) ** 2 <= (x1 - x2) ** 2 <= (r1 + r2) ** 2:
        return True
    return False


N = int(input())
circles = []
for _ in range(N):
    x, r = map(int, input().split())

    circles.append((x, r))

circles.sort()

for i in range(N - 1):
    circle1 = circles[i]
    circle2 = circles[i + 1]
    if is_meet(circle1, circle2):
        ans = 'NO'
        break
    ans = 'YES'
print(ans)

그러나..

ㅠㅠ 100% 부근에서 틀렸습니다 가 나와서 슬퍼하는 중...
그래도 게시판에 있는 반례가 내 코드에도 적용되어서(내 코드도 틀려서) 그나마 다행이라고 해야 하나..

나는 옆에 있는 원 두 개씩만 비교했다. 그러다 보니 이 그림처럼 바로 옆이 아닌데 교점이 존재하는 경우를 고려하지 못했다ㅠㅠ

맞았다! - 아이디어

위 그림 같은 경우를 처리하기 위해서 다시 고민에 빠졌다..
분홍색 원과 파란색 원은 일단 안 만나는 걸로 잘 처리가 되었고, 파란색 원과 초록색 원을 볼 차례를 더 생각해봐야했다.
파란색 원과 초록색 원이 포함관계(만나지 않는 경우 중 초록색 원이 내부에 있는 경우)인지 체크하고, 뭔가 처리를 해야했다. 그래서 원래 is_meet 함수는 True나 False만 리턴하다가, 내부에 있다면 Again도 리턴하게 했다.
Again인 경우에는 초록색 원과 분홍색 원도 비교했다. 그 두 원이 만나면 이제 그만 보고 NO를 출력하게 했다.

두 원이 만나지 않는다고 끝..! 하면 안됐다. 위 그림 같은 경우가 있을 수도 있으니까..!
혹시 한 원이 다른 원 내부에 있는지 체크해서, 그렇다면 더 뒤의(원의 중심 x가) 더 앞에 있는 원들도 보게 했다.

맞았다 ! - 코드

# 원의 중심 좌표 x 기준으로 정렬
# 옆에 있는 두 개 원씩 만나는지 보기
import sys

input = sys.stdin.readline

def is_meet(circle1, circle2):
    x1, r1 = circle1
    x2, r2 = circle2
    # if (x1 - x2) == 0 and r1 != r2: # 동심원
    #     return'Again'

    if (x1-x2)**2<(r1-r2)**2:
        return 'Again'
    if (r1 - r2) ** 2 <= (x1 - x2) ** 2 <= (r1 + r2) ** 2:
        return True
    return False


N = int(input())
circles = []
for _ in range(N):
    x, r = map(int, input().split())

    circles.append((x, r))

circles.sort()
def sol():
    for i in range(N - 1):
        circle1 = circles[i]
        circle2 = circles[i + 1]
        res = is_meet(circle1, circle2)

        if res == 'Again':
            j = i-1
            while j >= 0:
                circle3 = circles[j]
                res2 = is_meet(circle2, circle3)
                if res2 == 'Again':
                    j -= 1
                elif res2 == True:
                    return 'NO'
                elif res2 == False:
                    break

        elif res == True:
            return 'NO'
    return 'YES'
ans = sol()
print(ans)