[BOJ] 1654 - 랜선 자르기

이분 탐색으로 푸는 문제이다.

푸는 방법은 설명하지 않고, ‘잘 풀었는데 왜 틀렸지?’ 하는 경우에 점검해야 할 케이스를 적어보려고 한다.

난 오프라인 강의에서 이 문제를 어떻게 풀어야하는지 배웠는데도 불구하고 첫 제출에서 ‘틀렸습니다’를 맛봐야 했다…

이 문제의 조건을 잘 읽어보면, 다음과 같은 조건이 명시되어있다.

랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

당연히 int 범위에서 답이 나올 문제이고, 아무 생각 없이 int로 범위를 잡았는데 한 가지 문제가 있었다.

내가 이 문제에 접근한 방식은 1) 입력받은 랜선중 최대 길이를 max 변수에 저장 2) 최소값을 1로 가정하고 (min + max) / 2로 mid 값을 정해서 이분 탐색을 했는데, (min+max)가 2^31-1 을 넘어가는 케이스가 있다는 것이다.

간단하게 확인할 수 있는 케이스를 제시하면 다음과 같다.

2 1
2147483647
1

결국 나는 일부 변수 및 배열을 long으로 수정해서 제출했고 정상적으로 통과되었다.

얻은 교훈 : 문제 풀이 과정에서 발생하는 연산 도중에 int의 범위를 넘어가는 경우가 있는지도 잘 체크하자.