https://www.acmicpc.net/source/77333635

접근법

Brute-force

1. 큰 원을 찾는다.
2. 큰 원을 채울 수 있는 작은 원을 찾는다.
3. 작은 원을 채울 수 있으면 cnt+=2를 해준다.
4. 마지막 원 밖의 영역을 고려하여 cnt+1 을 프린트 해준다.

전체적인 접근법은 맞으나 당연하게도 N^2의 시간복잡도가 소요되어 시간초과가 날 것이다. 하지만 대략적은 접근법은 알 수 있다!

n이 최대 300,000 이므로 선형 탐색으로 문제를 해결해야 함을 알 수 있다!

Using Stack

처음에는 lst.append[a-b,a+b]) 로 시작, 끝 점만 받아서 처리하려고 하였으나 변수가 너무 많았다

정글 친구들의 도움을 받아 아래와 같이 접근하면 됨 알 수 있었다.

for i in range(n):
    a, b = map(int, input().split())
    lst.append([a - b, "("])
    lst.append([a + b, ")"])

시작점이 겹치고, 그 겹친 점이 큰 원의 내부를 채울 수 있다면 스택에서 Pop을 할 때 2를 cnt에 더해준다.

if lst[i][1] == '(' and lst[i][0] == stack[-1][0]:
            stack[-1][1] = 2

만약 중간에 이어지지 않는 원이 있다면, 가중치를 1로 변경한다.

elif (i+1 < boundary) and lst[i][0] != lst[i+1][0]:
	stack[-1][1] = 1

전체 코드

import sys

input = sys.stdin.readline

n = int(input())
lst = []
cnt = 0
for i in range(n):
    a, b = map(int, input().split())
    lst.append([a - b, "("])
    lst.append([a + b, ")"])

# lst.sort(key =  lambda x: (-x[1],x[0]), reverse= True)
# lst.sort(key = lambda x : (x[0],-x[1]))
lst = sorted(lst, key=lambda x: (x[0], -ord(x[1])))
stack = []
boundary = n*2

for i in range(0,boundary):
    if stack:
        if lst[i][1] == '(' and lst[i][0] == stack[-1][0]:
            stack[-1][1] = 2
        elif lst[i][1] == ')':
            cnt+=stack.pop()[1]
            if len(stack) == 0:
                continue
            elif (i+1 < boundary) and lst[i][0] != lst[i+1][0]:
                stack[-1][1] = 1
            continue
    stack.append([lst[i][0],1])

print(cnt+1)

# 16
# 0 20
# -19 1
# -9 9
# -17 1
# -15 1
# -13 1
# -11 1
# -9 1
# -7 1
# -5 1
# -3 1
# -1 1
# 1 1
# 7 5
# 11 9
# 16 4

# 6
# 2 2
# 1 1
# 3 1
# 10 2
# 9 1
# 11 1

# 6
# 2 2
# 1 1
# 3 1
# 10 3
# 9 1
# 11 1

https://www.desmos.com/calculator/ifg3mwmqun?lang=ko

문제 해결에 도움이 됐던 사이트!

소요시간 : 6시간

문제 해결을 위한 전체적인 접근법은 단 시간 내에 찾아냈지만, 구현을 함에 있어서 정말 많은 시간이 소요됐다.