1654번 랜선 자르기(이분탐색, 파라메트릭 서치) - ☆

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

<전략>

1. 주어진 랜선 중 가장 킨 랜선을 선택해서, 해당 랜선의 길이를 줄여서 어떤 길이가 되었을때, n개의 랜선을 만들 수 있는지 찾는 문제이다.

2. 파라메트릭 서치는, 정렬된 리스트에서 이분탐색을 적용하여 어떤 조건에 맞으면 절반의 범위를 계산하지 않고, 나머지 절반의 범위에서 계속 찾아가는 과정을 말한다.

※주의사항

1. 배열의 가장 작은 값으로 찾는다는 생각으로 처음에는 계속 틀렸었다. 이는 문제 이해를 잘못해서 발생한 일인데, 주어진 k개의 랜선을 모두 사용하는 것으로 착각했다. k개의 랜선을 모두 사용하지 않더라도, 가장 긴 랜선만 사용해서 n개의 랜선을 만들 수 있는 것도 정답인 것이다. 예를 들어, 길이가 각각 1 2 1000 인 랜선이 주어지고, 이 3개의 랜선을 이용해서 5개의 길이가 최대가 되면서 같은 랜선을 만드는 경우는 1000/5 = 200 이다. 즉, 길이가 1과 2인 랜선을 쓰지 않아도 된다는 말이다. 따라서, 정렬된 리스트에 맨 마지막 값을 기준으로 이분탐색을 진행해야 한다.

2. start 초기값이 0이 되어선 안된다. 경우에 따라 출력으로 0이 나올 수도 있기 때문.

3. count>=n 일때, start+1이 되므로, end를 출력해야 정답이 된다.

Code