사이트 #문제: 문제유형 / 난이도

문제 링크 : https://www.acmicpc.net/problem/2110

풀이 참고 : https://magentino.tistory.com/358#google_vignette

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

• 2차원 DP 는 시간 제한 걸림

• 문제 중요 조건은

  (1) N개 중 “C개 이상”의 공유기 설치하기

  (2) 공유기 설치한 집 중 “**최소 간격”**이 가장 큰 값을 출력하기

문제 유형 : 매개변수 탐색, 이진탐색

• 매개변수 = 최소간격 dist

• 매개변수’s 탐색 초기 범위= 0 ~ (arr[-1] -arr[0])

  goal) 탐색 범위 내에서 매개변수 “ 최소간격 Dist”로 “공유기 C개 이상 설치 가능” 한 Dist 최대값 찾기

• 최소 인접 거리 (매개변수 , dist) 가 감소하면 → 설치 가능한 공유기 개수 cnt 증가 [선형관계]

시간 복잡도 :

1. 집 리스트 순회하여 “최소간격 dist” 이상 거리로 설치 가능한 공유기 개수 구하기 ⇒ O(N)
2. “최소간격 dist”의 최대값 탐색 ⇒ 이진탐색 O(logN)

⇒ O(NlogN)