BOJ/1654_랜선 자르기

[문제]

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

[처음 생각]

입력되는 k개의 랜선의 길이가 2^31-1보다 작거나 같은 자연수이기 때문에 뭔가
 2로 나눠서 푸는 문제일 것 같은 느낌이었다...

[풀이]

이분 탐색으로 풀었다. 입력된 랜선 중에서 가장 긴 길이의 랜선을 찾아서 그 길이를 right로 놓고 left는 1로 두어서 mid값을 계산한 뒤, mid값으로 전체 랜선의 길이들을 나누었을 때 몫들의 합이 n보다 작다면 더 작은 수로 나눠야 하므로 right를 mid-1로 갱신하고 똑같이 반복한다. 

만약 그 몫들의 합이 n보다 크거나 같다면 result값에 일단 그 mid값을 넣고 left를 mid+1로 갱신한다. 몫들의 합과 같을 때와, 클때를 따로 나누지 않는 이유는 가장 긴 길이의 랜선을 얻기 위해서 계속해서 while 조건문을 만족할때까지 mid값을 구해서 결과를 얻기 위해서다. 처음에 result가 나오더라도 나중에 더 긴 길이의 랜선으로 n개로 나눌 수 있는 랜선이 나올 수 있기 때문이다. 

-> 이렇게 해도 틀렸다!!!

왜냐면 랜선의 길이가 int형 범위를 넘을 수 있고, 그것을 계산하는 left, right등의 변수 또한 int형 변수를 넘을 수 있기 때문에 모두 long형 변수로 바꿔줘야 한다!!!

[Code]

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1654/CutLan.java