공유기 설치_백준_2110

 

-문제-

 

 

 

 

-문제 접근-

 

 

이 문제는 집의 좌표가 주어졌을 때, C개의 공유기를 설치하여 가장 인접한 두 공유기 사이의 거리를 최대로 하는 문제입니다. 즉 가장 인접한 두 공유기 사이 거리가 최대가 되는 배치를 찾아야 합니다.

공유기 C개가 사이 거리 X이상이 되도록 배치가 가능한가? = True/False(bool) 판별 필요 = 이진 탐색 

 

 

1. 입력 받은 집 좌표를 오름차순 정렬

 

 

2. 탐색 범위 설정

-left(시작) 공유기 사이 간격의 최솟값

-right(끝) 가장 오른쪽 끝 좌표 - 가장 왼쪽 좌표(공유기 사이 간격 최대값)

 

 

3. 이진탐색 과정

mid = (left+right) /2  : 공유기 사이 최소 거리를 mid로 잡는다.

 

 

-C개 이상의 공유기 설치 가능

left = mid +1: 거리 간격 증가

-C개 공유기 설치 불가

right = mid -1: 거리 간격 감소

 

 

-전체 코드-

 

 

-코드 설명-

canPlaceRouters() 함수에 lastPos 이전 설치 위치를 기준점인 첫 집(좌표)으로 잡고 공유기의 수를 count로 기록하여주고

if문에서 lastPos에서 houses[i]까지의 거리가 간격(dist)이상 떨어진 집이라면 공유기를 설치하여 카운팅을 해줍니다.

그 후 lastPos를 갱신하고 반복문을 돌리면서 공유기 설치가 되는지 안되는지를 판별합니다.

 

 

main()

입력 받은 값을 저장하고 오름차순 정렬한 후 탐색 범위를 설정하고 이진 탐색 루프(while)을 통해서 최소 간격이 최대 간격보다 커져서 범위를 벗어나기 전까지 루프를 해주어서 범위 안에 간격을 루프해줍니다. 

mid를 공유기 사이 최소 간격으로 잡아서 이진 탐색을 진행하며 공유기 설치가 가능하면 간격의 범위를 늘려서 answer을 갱신하여 주고 마지막으로 성공한 간격을 출력을 합니다. 

 

 

 

-END-