퀵 정렬, 이진검색, parametric search 1 aggressive

문제는 더블릿 10 퀵 정렬, 이진검색, parametric search에 있는 aggressive입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/aggressive/aggressive.php?pname=aggressive

우리의 위치와 소의 수가 주어졌을 때 소를 배치할 경우 소와 소의 가장 짧은 거리가 최대가 되는 때의 거리를 구하는 문제입니다.

1부터 입력받은 우리의 최대 위치까지 우선 정렬을 해야합니다.  algorithm 헤더에 있는 sort를 이용했습니다.  이제 소를 놓을 수 있는 위치에 놓으면서 소와 소 끼리의 거리와 가능한지의 여부를 판단합니다.

소와 소 끼리의 거리는 0과 우리의 최대 위치의 반 부터 시작합니다.  그럼 대략 처음 값은 500000000이 될 것입니다.  이를 우리의 첫 위치+500000000와 다음 위치의 거리 비교에 사용합니다.  이 비교가 만약 다음 위치까지의 값이 더 크면, 이는 소와 소 사이의 거리로서 적당한 값으로 판단합니다.

값이 너무 커서 잘 모르겠으면 값을 낮춰봅니다.  문제 예제에서 3이었는데 위에서 만약 거리로서 처음 위치+5~를 한 값이 소의 전체 위치를 넘거나 소를 우리 내에 다 배치할 수 없을 정도로 큰 간격이면 최대값을 반으로 줄이고 (최소값 + 최대값)/2를 다음 거리로 사용합니다.  여기서 최소값이 구하려는 최소 간격 거리로 처음에는 0부터 시작합니다.  

다시 예제로 돌아와서 최소값 0, 최대값 12인 상태를 봅니다.  

소의 우리 배열을 ar이라고 할 때,

ar[0]+6과 ar[1]의 값을 비교합니다.

7과 2입니다.

거리가 더 멀기 때문에 다음 값을 한칸 뒤로 밀어줍니다.

ar[0]+6과 ar[2]의 값을 비교합니다.

7과 4입니다.

역시 미룹니다.

7, 8.

6을 거리로 사용해도 될 정도의 값입니다.

소의 수는 3마리이기 때문에 한번 더 해야합니다.

그럼 8의 위치부터 다시 계산합니다.

ar[3](8입니다.)+6, ar[4]

14와 9입니다.

거리가 너무 멉니다.

그럼 ar[5]와 비교를 해줘야 하는데 ar[5]는 없고 아직 배치해야할 소는 남아있기 때문에 결국 6은 간격으로 부적합합니다.

0+12에서 6이었으니 최대값을 반으로 나눠 다시 해봅니다.

(0+6)/2=3.  예제에서 정답이었던 3으로 해보겠습니다.

ar[0]+3, ar[1]

4, 2 : 아직 안됩니다.

4, 4 : 같거나 뒤가 크면 ar[0]인 1과 ar[2]인 4 사이에 거리 3이 적당하다는 것을 나타냅니다.

3은 적당하기 때문에 a[0]과 ar[2]에 소를 배치하고 남은 소를 배치해 봅니다.

ar[2]+3, ar[3]

7, 8 : 이전 소의 위치 4와 여기에 거리값을 더한 7보다 다음 소의 위치 8이 더 멀기 때문에 여기서도 3은 적당한 값입니다.

8은 소의 우리 범위 내에 있고 모든 소를 배치하였기 때문에 결국 3은 적당한 거리값입니다.

이 값은 거리 최소값에 넣습니다.

다음 계산은 다음과 같습니다.

(3+6)/2.

거리는 4가 됩니다.  

4를 이용해 위의 과정을 반복합니다.

이를 최대값과 최소값의 차이가 1보다 크면 계속 해줍니다.  

이 과정이 끝난 후의 최소값이 소를 놓을 수 있는 최소거리의 최대값이 됩니다.