일반적인 세그먼트 트리 문제이길래, 세그먼트 트리를 구현하고 당연히 맞을 줄 알았는데 틀렸다. 문제에서 입력은 int형 범위랬지만 구간 합은 long long이 될 수 있을테니 long long을 사용했는데도... 그래서 다른 분의 블로그를 찾아봤는데, x번째에서 수에서 y번째 수까지의 합을 구하는 것에서 x<=y가 아닐 수도 있다....고 한다.
예전에 처음 세그먼트 트리를 풀고 다른 분의 코드에서 x<=y가 아닌 경우를 가정해서 구현된 것을 보고 나도 주의해야지 생각했던 것인데...
x>y인 경우 swap을 해서 냈는데, 또 WA를 받았다. 원인을 보니... swap함수를 만들 때, parameter를 포인터나 참조자를 쓰지않고 그냥 복사해서 넘기는 식으로 해버렸다...
결국 AC를 받았다.
FenwickTree로도 풀어봐야겠다.
오히려 FenwickTree로 할 때 더 고생했는데... 여러가지 함정이 있겠지만 가장 찾기 힘든 함정에 대해 써보겠다.
FenwickTree의 경우 point update를 할 때, 해당하는 숫자를 바꿔주는 것이 아니라 원래 숫자와의 차이만큼 더해주는 식으로 하는데, 입력으로 int형 정수가 주어져도 양의 정수와 음의 정수로 주어질 경우 그 차이값이 int형 범위를 넘을 수 있다! 그렇기 때문에 그 부분을 long long으로 처리해 줘야 한다.
물론 이런 문제들은 모든 변수를 long long으로 처리하면 일어나진 않겠지만... 주의해야할 점이다.
댓글 없음:
댓글 쓰기