[백준] (10000) 원 영역 [Python]

🔗 문제 링크

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

문제

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

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

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

입력

첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다.

다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109)

입력으로 주어지는 원은 항상 유일하다.

출력

첫째 줄에 원으로 인해서 만들어지는 영역의 개수를 출력한다.

테스트 케이스

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

---

서로 다르게 색칠할 수 있는 영역의 수를 구하는 문제!

💻 나의 코드

1st Try:

import sys
input = sys.stdin.readline

n = int(input())
arr = list()

for _ in range(n):
    x, r = map(int, input().split())
    arr.append((x-r, 1)) # (
    arr.append((x+r, 0)) # )

arr.sort(key = lambda x: (x[0], x[1]))

stack = list()
answer = 1
minus = 0

for a, b in arr:
    if b == 1: # (
        stack.append((a, "("))

    elif b == 0: # )
        if stack[-1][1] == "(":
            stack.pop()
            stack.append((a, "○"))
        elif stack[-1][1] == "○":
            if stack[-1][0] == a:
                tmp = 0
                while stack[-1][1] == "○":
                    stack.pop()
                    tmp += 1
                stack.pop()
                stack.append((a, tmp * 2))
            else:
                minus += 1
                tmp = 0
                while stack[-1][1] == "○":
                    stack.pop()
                    tmp += 1
                stack.pop()
                stack.append((a, tmp * 2))
            
        elif type(stack[-1][1]) == int:
            tmp = 0
            while stack[-1][1] != "(":
                _, t = stack.pop()
                if t == "○":
                    tmp += 1
                else:
                    tmp += t
            stack.pop()
            stack.append((a, tmp * 2))

for _, b in stack:
    if b == "○":
        answer += 1
    elif type(b) == int:
        answer += b

print(answer - minus)

괄호의 값(2504) 문제를 풀듯이 괄호 안에 있는 괄호쌍()을 작은 원 ○으로 치환하는 방식으로 접근하였다. (참고)

중복되는 값을 제하고 남은 스택의 길이를 이용해 계산식도 만들어서 문제를 풀었지만 계속해서 2% 부근에서 틀렸습니다!를 받았다.😔

2nd Try:

import sys
input = sys.stdin.readline

n = int(input())
arr = list()

for _ in range(n):
    x, r = map(int, input().split())
    arr.append((x-r, 1)) # (
    arr.append((x+r, 0)) # )

arr.sort(key = lambda x: (x[0], x[1]))
#print(arr)

stack = list()
answer = 1

for a, b in arr:
    if b == 1: # (
        stack.append((a, "("))

    elif b == 0: # )
        ww = 0
        while stack:
            tmp = stack.pop()
            if tmp[1] == "(":
                w = a - tmp[0]
                answer += 2 if w == ww else 1
                stack.append((w, "○"))
                break
            
            elif tmp[1] == "○":
                ww += tmp[0]

print(answer)

 

의외로 정답으로 가는 접근 방식은 단순했다. 굳이 복잡하게 계산식을 세울 필요도 없이, 그냥 큰 원 내부의 원들의 지름의 합이 큰 원의 지름보다 작으면 영역에 +1을, 같으면 +2를 해주면 되는 것이었다.

위에서 두번째 시도라고 적기는 했지만, 사실은 엄청난 시행착오를 겪었다.😵