BOJ 1654

랜선 자르기 문제는 이분 탐색으로 비교적 쉽게 풀 수 있는 문제인데,
음... 자료형이 문제였다...

일단 입력값 범위는 2의 31제곱 -1로 int범위이다. 그런데 랜선의 개수를 세는 과정에서
int형 범위를 넘을 수도 있을 것 같아 그 부분은 long long으로 바꿨는데, 그래도 틀렸다고 나와서 전부(입력부터 모두 다) long long으로 바꿔 버렸더니 맞다고 나오길래...

처음에는 문제가 잘못된건가 했다. 그래도 혹시 몰라서 질문을 뒤져봤는데 그리 명쾌한 답변은 없어서, (물론 나중에 이유를 알고 생각해보니 그런 답변이 있었는데 지나친 것 같다.) 게시판에 직접 질문을 올렸는데, 거의 바로 답변이 달렸다.

orange4glace님의 감사한 답변이다.


mid값을 구하는 과정에서 l+r이 int범위를 초과할 수 있다.
그래서 순간 아하! 깨달음을 얻었다 생각했는데 더 생각해보니
음 그래도 l+r이 초과하는거지 (l+r)/2는 결국 int형 범위를 초과하지 않게되는데...

그래서 직접 실험해봤다.

이렇게 해보니 값이 출력되지 않는다... 으흠 그래서 막 바꿔서 이것저것 해보았는데,
결국은 l, r을 long long으로 바꾸니 제대로 나왔다.

정확히는 모르겠지만, long long범위가 되는 연산을 하려면 l, r도 long long이여야 하는 것 같다. (물론 시스템 차이라던가, 아니면 내가 모르는 무언가로 인해 다를 수 있기 때문에 일단 이렇게 기록해두고 정확한건 나중에 공부하면서 알아가자.)

그래서 이번에는 l, r만 long long으로 바꾸고, mid, ans는 int형으로 해보았는데..
이번에는 런타임 에러가 떴다. 직접 실험해보니...
while문 조건 중에 while(l <= r)이라는 조건이 있다. 참고로 l < r로 할 경우 모든 수를 다 볼 수 없다. 여하튼 이 조건 때문에 l값이 int형 범위를 넘어갈 수 있고, 그로인해 mid값도 int형 범위를 넘어가게 될 수 있다. (예 : l : 2,147,483,648(int범위 초과) r : 2,147,483,647)

아 그리고 추가로 long long을 쓸 때와 int를 쓸 때 속도나 메모리 차이가 좀 날 것이다.
이 문제에서는 속도차이는 큰 차이 없었는지 보이지 않고 4ms로 나왔지만 메모리 차이는 확실히 나왔다. 
이 문제를 통해 이분 탐색 외에도 많은 것을 배웠다.
-----------------------------------
오랜만에 다시 봤더니 재채점이 되어있고 원래 AC를 받았던 코드가 런타임에러를 받아서 살펴봤는데... 원인은 이분탐색에서 l, r값 설정이었다. l을 0으로 설정해놨는데, 이러면 mid값이 0이 될 수 있고, 랜선의 개수를 계산할 때 0으로 나누는 연산이 실행되어 런타임에러가 난 것 같다.