이분 탐색. [1654]

[1. 문제 설명]

 

 

 

[2. 풀이 접근]

첫번째 접근 (틀린 풀이)

1. 전체 랜선 중 최소 길이를 찾는다. => A
2. [1, A] 범위로 하여 랜선의 길이를 이분 탐색 한다.
3. 전체 랜선의 개수가 조건에 만족하는지 확인한다. (랜선 개수가 더 많은 것은 중요하지 않다.)
4. 이분 한 값이 이전에 최대 랜선 길이보다 더 길 경우 교체한다.

위 접근이 틀린 이유는 전체 랜선 중 최소가 랜선길이의 상한 값이 되었기 때문이다.

K 개의 랜선이 각각 [100, 100, 100, 1] 인 경우 왠만하면 필요한 랜선 N 개를 만족하지만,

랜선의 길이는 고작 1밖에 되지 않기 때문이다.

 

이 경우 1짜리 랜선을 버리는 것이 더 낫다.

 

따라서, 위 접근에서 A 를 전체 랜선 중 최대 길이로 해야 올바른 접근이 된다.

 

랜선의 최대 길이는 2^32 정도 되는데,

이분 탐색해봤자 최대 32번의 연산이 발생하기에, 거의 상수 시간 정도로 봐도 되기 때문에,

시간 복잡도에 큰 영향은 없다고 본다.

 

 

[3. 코드]