[코딩테스트 연습] 기지국 설치

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12979

---

N제한이 2억,

배열의 크기 10,000

W제한은 10,000 입니다.

 

큰 숫자 제한을 보면, 단순히 선형탐색만 해도 시간초과가 난다는 걸 알 수 있습니다.

그러므로 선형탐색보다 더 빠르게 탐색을 해야 답이 나오는 걸 알 수 있습니다.

즉, 로그 시간 탐색을 하거나 단순 숫자 계산만으로 해결해야 합니다.

 

제가 해결한 아이디어입니다.

 

시작좌표를 0으로 잡고, 전체 station 을 순회합니다. (오름차순 정렬이 되어있으므로)

 

1. "시작좌표 ~ station[i] 기지국이 커버하는 범위의 하한"을 구합니다.

 

2. 이 범위 사이에 몇 개의 기지국이 필요한 지 구합니다.

 

3. 그리고 나서 시작좌표를 "시작좌표 = station[i] 기지국이 커버하는 범위의 상한" 으로 갱신합니다.

 

4. 1번을 다시 반복합니다. (갱신된 시작좌표 ~ station[next] 기지국이 커버하는 범위의 하한 구하기) 

 

 

2번같이 몇 개의 기지국이 필요한지는 아래의 계산을 통해 쉽게 구할 수 있습니다.

int NEED = DIST / (2*W + 1 )

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter04.cc