겹치지 않는 원
면접 대비시간 제한1초메모리 제한128 MB
x축 위에 중심이 있는 N개의 원이 주어질 때, 남는 원들이 서로 겹치지 않도록 제거해야 하는 최소 원의 개수를 구하는 문제로 사실상 구간 스케줄링 문제입니다.
문제
x축 위에 중심이 있는 원 N개가 있다. i번째 원의 중심의 x좌표는 C_i이고, 반지름은 R_i이다.
일부 원을 지워서 남은 모든 원이 서로 교차하지 않게 하려고 한다. 두 원이 한 점에서 접하기만 하는 경우는 교차하지 않는 것으로 본다.
주어진 원들 중에서 최소 몇 개를 지워야 하는지 구하라.
입력
첫째 줄에 원의 개수 N이 주어진다. (1 <= N <= 1,000)
다음 N개의 줄에는 두 정수 C_i와 R_i가 주어진다. C_i는 i번째 원의 중심의 x좌표이고, R_i는 그 원의 반지름이다. (1 <= C_i, R_i <= 100)
중심 좌표와 반지름이 모두 같은 두 원은 주어지지 않는다.
출력
모든 남은 원이 서로 교차하지 않게 만들기 위해 지워야 하는 원의 최소 개수를 출력한다.