P5676

[baekjoon-5676] 음주 코딩

오버플로우 이슈

처음에는 Segment Tree에 모든 값들을 저장하고 곱해서 풀었다. 그랬을 때 틀렸습니다!를 볼 수 있었고, 문제의 범위를 보니 최대의 절댓값 100, 수열의 크기는 10^5로 최댓값으로는 100을 10^5번 곱할 수 있다는 것인데, 거의 상상 초월로 큰 수가 나올 수 있다. 다음의 예시만 살펴봐도 그렇다.

// Input
10 1
100 100 100 100 100 100 100 100 100 10
P 1 10
// Output (Debugging)
[-1981284352, 1410065408, 1000000000, 1000000, 10000, 1000000, 1000, 10000, 100, 100, 100, 10000, 100, 100, 10, 100, 100, 0, 0, 0, 0, 0, 0, 100, 100, 0, 0, 0, 0, 0, 0, 0]
-1981284352
-

배열에는 양수밖에 담지 않았는데, 음수의 결과가 나오는 것을 볼 수 있다.

따라서 이 문제는 값이 아닌 부호로 풀어야 한다. 출력값으로 부호만을 요구하는 이유가 다 있다. ㅎㅎ 나는 1, -1, 0 으로 값을 저장하여 문제를 풀었다.

재밌다. 너무 재밌는 문제다.