[BOJ] 1654번: 랜선 자르기

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

amount[len]을 랜선 조각의 길이가 len일 때 랜선의 갯수라고 할 때 amount는 increasing sequence입니다.(monotonic임은 성립하지 않음) 즉, x > y이면 amount[x] >= amount[y]입니다.

이를 통해 amount[x] >= N인 최대의 x를 이분탐색으로 찾으면 되는데, 주의할 점이

i) amount[x] = N을 찾았다고 해서 x를 바로 출력하면 안됩니다. amount[x] = N을 만족하는 x는 여러개일 수 있고 그 중에서 최댓값을 출력해야하기 때문에 이분탐색을 계속 수행해야합니다.

ii) amount[x] = N인 x가 존재하지 않을 수도 있습니다.(ex - K = 2, N = 2, 랜선의 길이 : 1, 2)

iii) int 범위를 초과할 수 있습니다.(ex - 랜선의 갯수 : 1000개 랜선의 길이 : 2^31-1, 랜선 조각의 길이 : 1)

이 세가지를 조심해서 이분탐색을 수행하면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/1654.cpp