1654번 - 랜선 자르기
문제 자체가 단순해서 반례랄께 따로 없긴 하지만,
몇 가지 간과할 수 있는 사실들이 있어서 댓글을 남겨봅니다.
1. ~(1<<31)의 고려
이 괴상한 숫자는 자연수 231-1 = 2147483647을 나타냅니다.
1 1
2147483647
이 입력될 경우, 2147483647을 출력해야 합니다.
이것도 답이 될 수 있으니,
이 킹갓 블로그 (https://www.acmicpc.net/blog/v...)를 참고해서 이진탐색으로 푸셨다면 (안하셨다면 참고 추천드립니다), 세 줄 요약의 1번조건을 잘 생각해보세요.
위의 예시는 이진탐색의 'hi'를 2147483647 등으로 해야 한다는 것, 그리고 애초에 그전에 2147483647이 답이 될 수 있는지부터 체크해야 함을 나타냅니다.
2147483647이 답이라면 Check(hi)도 Check(lo)와 같을 테니까요.
2. 오버플로우 발생 가능성 고려 (필자는 이것때문에 40-50퍼에서 틀렸어요...)
32비트 signed int형을 사용하셨다구요? 좋아요! 그렇게 해서 풀 수 있습니다! 저도 그렇게 풀었구요.
그런데 이진 탐색 과정에서 다음과 같은 연산을 한 번쯤 하셨을 겁니다.
int mid = (s+e)/2;
자, e는 2147483647이 될 수 있죠. 그리고 또 s도 거의 2147483646까지도 가능합니다!
중요한 점은 우리가 숫자를 더해서 오버플로우가 발생했다는 것입니다!
그리고 오버플로우가 일어날 때에는 s+e가 음수가 되고,
음수를 비트 right shift 연산을 때리면 가장 왼쪽 MSB(Most Significant Bit)가 0이 아니라 1이 된다는 것입니다!
한마디로 여러분의 연산결과가 음수가 된다는 뜻입니다.
그게 문제라는 것을 못 믿으시겠다구요? 아니, 걍 생각하면 MSB까지 shift될텐데, 뭐가 문제냐고요?
저도 못 믿어서 아래 C++ 코드를 돌려보니 저의 경우는 저렇게 나오네요...
cout << (-8>>1); // NOT 엄청난 '양수', but -4! => NOT 0 extend to MSB, but 1 extend! => 단순 (s+e)/2는 오버플로우 발생 가능!
이게 문제가 된다는 것을 깨닫고 오버플로우 문제를 해결하니 제 반례를 통과했습니다.
이제 아래 반례를 잘 참고하시고 (s+e)/2를 오버플로우 안나게 계산하는 방법을 한번 생각해보시기 바랍니다!
참고로 저는 (s+e)/2를 ((s^e)>>1)+(s&e) 로 계산했습니다.
0과 1이 있는 자릿수 비트는 1로 만들어서 2로 나누고,
1이 겹치는 자릿수 비트는 2로 나눠도 그대로니까 그대로 더했어요.
이것 말고 또다른 방법을 사용하셨다면 댓글 한 번만 달아주세요!
저는 (0.5 * s + 0.5 * e) 로 연산하는 방법 사용했습니다.
댓글을 작성하려면 로그인해야 합니다.
calculus 2년 전 8
문제 자체가 단순해서 반례랄께 따로 없긴 하지만,
몇 가지 간과할 수 있는 사실들이 있어서 댓글을 남겨봅니다.
1. ~(1<<31)의 고려
이 괴상한 숫자는 자연수 231-1 = 2147483647을 나타냅니다.
1 1
2147483647
이 입력될 경우, 2147483647을 출력해야 합니다.
이것도 답이 될 수 있으니,
이 킹갓 블로그 (https://www.acmicpc.net/blog/v...)를 참고해서 이진탐색으로 푸셨다면 (안하셨다면 참고 추천드립니다), 세 줄 요약의 1번조건을 잘 생각해보세요.
위의 예시는 이진탐색의 'hi'를 2147483647 등으로 해야 한다는 것, 그리고 애초에 그전에 2147483647이 답이 될 수 있는지부터 체크해야 함을 나타냅니다.
2147483647이 답이라면 Check(hi)도 Check(lo)와 같을 테니까요.
2. 오버플로우 발생 가능성 고려 (필자는 이것때문에 40-50퍼에서 틀렸어요...)
32비트 signed int형을 사용하셨다구요? 좋아요! 그렇게 해서 풀 수 있습니다! 저도 그렇게 풀었구요.
그런데 이진 탐색 과정에서 다음과 같은 연산을 한 번쯤 하셨을 겁니다.
int mid = (s+e)/2;
자, e는 2147483647이 될 수 있죠. 그리고 또 s도 거의 2147483646까지도 가능합니다!
중요한 점은 우리가 숫자를 더해서 오버플로우가 발생했다는 것입니다!
그리고 오버플로우가 일어날 때에는 s+e가 음수가 되고,
음수를 비트 right shift 연산을 때리면 가장 왼쪽 MSB(Most Significant Bit)가 0이 아니라 1이 된다는 것입니다!
한마디로 여러분의 연산결과가 음수가 된다는 뜻입니다.
그게 문제라는 것을 못 믿으시겠다구요? 아니, 걍 생각하면 MSB까지 shift될텐데, 뭐가 문제냐고요?
저도 못 믿어서 아래 C++ 코드를 돌려보니 저의 경우는 저렇게 나오네요...
cout << (-8>>1); // NOT 엄청난 '양수', but -4! => NOT 0 extend to MSB, but 1 extend! => 단순 (s+e)/2는 오버플로우 발생 가능!
이게 문제가 된다는 것을 깨닫고 오버플로우 문제를 해결하니 제 반례를 통과했습니다.
이제 아래 반례를 잘 참고하시고 (s+e)/2를 오버플로우 안나게 계산하는 방법을 한번 생각해보시기 바랍니다!