PS/백준
[백준] (10000) 원 영역 [Python]
munsik22
2025. 3. 24. 15:42
🔗 문제 링크
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를 해주면 되는 것이었다.
