랜선 자르기
Prob
K개의 랜선을 N개의 모두 같은 길이의 랜선으로 만들 수 있는 랜선 최대 길이
N개보다 많이 만드는 것도 N개를 만드는 것에 포함
Solv
K개의 랜선 X에서 mid를 나누어 모두 더한 값을 n이라 할 때,
n이 N이 되는 값 이분 탐색
low는 1로 high는 X의 총합에서 N을 나눈 값으로 설정
n\(>=\)N인 경우 low = mid+1
n\(<\)N인 경우 high = mid-1
low > high 일때까지 반복
Check
K=4 N=11
lan=[802 743 457 539]
| mid | low | high | n |
|---|---|---|---|
| 116 | 1 | 231 | 19 |
| 174 | 116+1 | 231 | 13 |
| 203 | 174+1 | 231 | 10 |
| 188 | 175 | 203-1 | 11 |
| 195 | 188+1 | 202 | 11 |
| 199 | 195+1 | 202 | 11 |
| 201 | 199+1 | 202 | 10 |
| 200 | 200 | 201-1 | 11 |
| 200 | 200+1 | 200 | 11 |
K=3 N=4
lan=[11 11 2]
| mid | low | high | n |
|---|---|---|---|
| 3 | 1 | 6 | 6 |
| 5 | 3+1 | 6 | 4 |
| 6 | 5+1 | 6 | 2 |
| 6 | 6+1 | 6 | 2 |
K=2 N=4
lan=[50 200]
| mid | low | high | n |
|---|---|---|---|
| 31 | 1 | 62 | 7 |
| 47 | 31+1 | 62 | 5 |
| 55 | 47+1 | 62 | 3 |
| 51 | 48 | 55-1 | 3 |
| 49 | 48 | 51-1 | 5 |
| 50 | 49+1 | 50 | 5 |
| 50 | 50+1 | 50 | 5 |
