[BOJ] 백준 1654. 랜선 자르기

▶문제설명

[BOJ] 1654. 랜선 자르기

https://www.acmicpc.net/problem/1654

▶Hint

---

이분탐색 문제이다. 

이분 탐색 문제는 일반적으로 값의 범위는 넓지만 특정 값을 미리 정해놓고 시뮬레이션 해보는 것이 가능한 문제에 적용이 가능하다.

( 1 <= 랜선의 길이 <= 2^31-1 ) 라고 했으므로 int 자료형의 최대값을 넘지 않는다.

따라서 초기 시작 값 left를 1, right를 2^31-1 로 두고  이분탐색을 수행하면 된다.

mid = (left+right) / 2; 연산을 수행해서 얻은 mid 값이 주어진 랜선들을 잘라낼 길이가 되는데, 주어진 랜선들을 mid 값으로 나눈 값의 누적 합이 N이 되는 mid 값들 중 최대가 되는 mid 값을 구하면 된다. 

쉽게 말해서 범위 내에서 가능한 mid 값을 모두 탐색 하면서 조건을 만족하는 최대 mid 값을 찾아내는 문제이다.

▶시간 복잡도

---

이분 탐색은 탐색에 O(logN)의 시간 밖에 걸리지 않는 빠른 탐색 알고리즘이다. 

랜선 길이가 최대 값인 2^31-1이라고 해도 최대 약 31번 만에 탐색이 완료되어 정답을 찾을 수 있게 된다.

매번 K개의 랜선을 mid 값으로 나눈 값의 누적합을 구해 보아야 하므로 전체적인 시간 복잡도는 O(K*logN)이 된다.

(1 <= K <= 10000) 이므로 제한 시간 내에 해결이 가능하다.

▶Solution