import sys
N = int(sys.stdin.readline())
points = []
for _ in range(N):
x, r =list(map(int, sys.stdin.readline().split()))
points.append(["{", x - r, 0, 0])
#괄호, 좌표, 상태(이어지면 1 아니면 0), 이어진 원 지름 길이의 합
points.append([")", x + r, 0, 0])
points.sort(key=lambda x:(x[1], x[0]))
stack = []
answer = 1
for i in range(len(points)):
if points[i][0] == "{":
if stack:
if stack[-1][1] == points[i][1] or stack[-1][3] == points[i][1]:
stack[-1][2] = 1
else:
stack[-1][2] = 0
stack.append(points[i])
else:
half = stack.pop()
if stack and stack[-1][2] == 1:
stack[-1][3] = points[i][1]
if half[2] == 1 and half[3] == points[i][1]:
answer += 1
answer += 1
print(answer)풀이
원이 서로 교차하지 않는 다는 조건 덕분에 원으로 만들어 지는 영역을 구하는 방법은 간단하다.
원이 만들어질 때마다 새로운 영역은 무조건 하나가 추가되고 아래와 같이 원 내부의 원들이 빈 공간 없이 접해있을 때 새로운 영역이 하나 더 추가된다.(큰 원의 위아래 공간)
여기저기 찾아보니 나머지는 알겠는데 각 원들의 내부가 원들로 끊김없이 접하는지 아닌지를 어떻게 판단할지 감이 오지 않았다. 그래서 각 원의 시작점에 무작정 저장하기로 결정했다.
points.append(["{", x - r, 0, 0])
그래서 각 점마다 원의 시작점인지 아닌지(스택 느낌을 살리기 위해 괄호를 사용했다.), 점의 좌표, 원이 끊임없이 접해지는 상태인지 아닌지, 어디까지 이어졌는지를 같이 저장했다.
이후 풀이는 이렇다.
1) 원의 시작점( "{" )이 들어올 때 스택에 다른 시작점이 저장되어 있다면 스택에 저장된 마지막 시작점(바로 앞 시작점)과 서로 좌표가 같은지(접하는지)를 확인한다.
if stack[-1][1] == points[i][1]
이때 접한다면
stack[-1][2] = 1
원이 접하는 상태라고 바꿔주고,
접하지 않는다면
stack[-1][2] = 0
상태를 유지하거나 접하지 않는 상태라고 바꿔준다.
2) 원의 끝점( ")" )이 들어올 때 스택에서 시작점을 빼주고
스택 내 다른 점이 있다면 금방 뺀 시작점이 바로 앞에 저장된 시작점과 접해있는지를 확인한다.
if stack and stack[-1][2] == 1
만약 접해있다면
stack[-1][3] = points[i][1]
앞 시작점 '어디까지 이어졌는지를 저장하기 위한 공간'(3번 인덱스)에 접해있는 원의 끝 점을 저장해준다.
이제 다음에 들어오는 시작점은 방금 저장한 점이나 시작점 둘 중 한곳에 접해있는지를 확인하면 되므로 시작점이 들어올 때 조건문에 조건을 추가해준다.
if stack[-1][1] == points[i][1] or stack[-1][3] == points[i][1]
그리고 만약 1. 스택에서 꺼낸 시작점이 끊김없이 접해졌고 2. 마지막으로 접해진 원의 끝점이 본인의 끝점과 같은 경우
if half[2] == 1 and half[3] == points[i][1]:
answer += 1
처음부터 끝까지 끊김없이 접해졌다는 것이므로 영역을 하나 더 추가해준다.
마지막으로 원이 하나 생길 때마다 영역은 무조건 하나씩 생기기에 모든 만들어진 원에 대해 영역을 하나씩 추가해준다.
설명이 만족스럽지도 않고, 백준에서 테스트 시간도 거의 꼴등에 가깝지만 파이썬 풀이가 거의 없기도 하고 문제가 신기해서 올려보게 되었다.
모든 피드백 환영합니다.
-끝-
