백준 10000 원 영역 파이썬

x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다.

원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오.

영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다.

예제 입력	예제 출력
2 1 3 5 1	3
3 2 2 1 1 3 1	5
4 7 5 -9 11 11 9 0 20	6

 

문제 바로가기

---

문제 해석

문제를 보면, 원은 서로 교차하진 않지만 접할 수 있다고 했다. 우리는 원으로 만들어지는 영역의 개수를 구하면 되는 것이기 때문에 원이 완성됐을 때 개수가 하나 추가되는지, 두개 추가되는지를 판단하면 된다. 접하는 두원의 지름 합이 바깥원의 지름과 같으면 영역이 두군데가 생기기 때문이다. 즉, 원들의 지름값도 계산을 해야 한다.

 

문제 풀이

전에 백준 괄호 문제, 괄호의 값 문제를 푼 적 있다. 이 문제도 괄호와 비슷하게 풀면 된다. 원의 왼쪽과 오른쪽을 마치 왼쪽 괄호와 오른쪽 괄호로 취급하여 판단한다. 원의 왼쪽과 오른쪽을 나눠 다른 원과 접하는지 아닌지를 판단하는 것이다. 나는 이것을 L과 R로 구분했다. L이면 스택에 넣고, R이면 스택에서 뺀다. 내부원은 C로 구분한다. 개수를 2개 더해준 후 다시 스택에 내부원으로(C) 넣어줘야 지름을 누적 계산할 수 있다.

 

전체 코드

import sys
input = sys.stdin.readline

n = int(input())

values = []
for _ in range(n):
    c, r = list(map(int, input().split()))
    values.append(["L", c-r])
    values.append(["R", c+r])
values.sort(key=lambda p: (-p[1], p[0]), reverse=True)

stack = []
count = 1

for value in values:
    if value[0] == "L":
        stack.append(value)
    else:
        cum_width = 0

        while stack:
            prev = stack.pop()

            if prev[0] == "L":
                width = value[1] - prev[1]

                # 너비가 같으면 +2
                if width == cum_width:
                    count += 2
                else:
                    count += 1

                stack.append(["C", width]) 
                break

            # 내부원
            elif prev[0] == "C":
                cum_width += prev[1]
    
print(count)