[백준][이분탐색] 1654번 랜선자르기

문제

K개의 랜선을 잘라서 N개의 같은 길이의 랜선을 만드시오. 이 때 만들 수 있는 최대 랜선의 길이를 구하시오.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1654)

풀이 

이분탐색의 감을 익혔다고 생각하고 더 어려운 문제를 골랐더니 잘 못풀겠어서 한번 더 복습하기 위해 이 문제를 골랐습니다. 여느 이분탐색 문제처럼 보였고 앞에서 풀던대로 틀었더니 너무 틀렸습니다를 많이 받았습니다. 이분탐색을 하며 mid 값으로 랜선을 잘랐을 때 같은 길이의 랜선이 몇개가 되는지 확인을 하고, N개보다 많다면 더 길게 잘라주도록 범위를 수정하고 더 적다면 더 짧게 잘라주도록 합니다. 알고리즘 자체는 이분탐색을 써주면 되는데 입력되는 범위가 크다보니 오버플로우를 잘 체크해줘야합니다. (long long type으로 해주면 됩니다.) 이분탐색에서 low, high, mid 를 계산할 때 저는 주로 mid의 값을 low, high에 바로 대입해서 마지막에 정답은 low 또는 high로 출력할 수 있게 짜는 편인데, 그렇게 하다보니 예외적인 상황에서 처리를 못하게 짜져있었습니다. 이 문제에서 N이 1일 경우에는 가장 큰 랜선의 길이가 최대 길이로 되는데 저는 while문 조건에서도 low+1<high 로 해두었고, (low == high일 수 없도록) 마지막 정답은 low로 출력했기 때문에 이런 경우에는 high가 출력되어야 하는데 잘못 구현되어 있었습니다. 대부분 이분탐색 구현코드들을 봤을 때도 while(low <= high), low = mid+1, high = mid-1 로 가장 많이 작성되는 걸 알 수 있었는데 아무래도 low == high와 같은 상황도 존재할 수 있기 때문에 이렇게 구현하는 것이 더 안전한? 방법인 것 같다고 생각이 들었습니다. 

+ 신중히 올린다 했는데 분명.. 타입때문에 오버플로우나서 생긴 에러인 줄 알고 계속 제출하다보니 이렇게 많은 틀렸습니다를 받아버렸습니다. 앞으로는 더 신중히.. 한줄한줄.. 열심히 짜야겠습니다.

코드

https://github.com/kswim/Algorithm/blob/master/BinarySearch/1654.cpp