BOJ 11658 구간 합 구하기3

백준님의 풀이 슬라이드를 보고 풀었다.

처음에 고민할 때는 2차원배열의 각 칸에 번호를 매겨서 segment tree혹은 fenwick tree로 풀려고 했는데, 그러면 조금 복잡해질 것 같기도하고 해서 고민하다가 그냥 풀이 슬라이드를 보니... 2D Fenwick tree란 것이 있었다.

막 와닿지는 않는데, 대충(?) 살짝 억지로 이해하고 넘어가는 중이다...
문제도 그 풀이대로 풀었다.

탑코더 페이지에 보면 좋은 그림이 하나 있긴한데, 그 그림을 봐도 이해가 되고, 와닿는 것은 아니지만 일단 참고하면 좋을 것 같다.
Fenwick Tree(in topcoder community)

그리고 문제를 푼 후 dotorya님의 코드를 봤는데, 넓이를 구할 좌표 2개를 입력 받고
좌표의 크기를 비교한 후 swap시키는 코드가 있었다. 생각해보니 문제 조건에
x1, y1, x2, y2가 주어졌을 때, (x1 <= x2 && y1<= y2) 라는 조건이 없다! 그렇다면 dotorya님의 방식대로 해주어야 한다!

난 별 생각 없이 ....당연히 저 조건을 만족하는 입력만 들어올 것이라고 막연하게 생각하고 있었던 것 같다.
항상 조건을 잘 보고, 그에 맞는 코드를 짜도록 하자!

2016년 9월 22일 추가+
오늘 BOJ Slack에서 이 문제에 대한 appa님의 풀이를 보게 되어서 그렇게 풀어보고 여기 간단히 정리해보려고 한다.


 

appa님의 설명이 정말 잘 돼있어서 굳이 내가 뭘 쓸 필요가 없을 것 같다. 그리고 이 풀이로 AC를 받기 전까지 몇 번 틀렸는데 그 이유는 누적합을 update해준 후, 배열의 값을 update해주지 않아서 였다. 주의하도록 해야겠고, 확실히 이렇게 푸는 것이 훨씬 쉬운 것 같다. 물론 속도는 좀 더 느리게 나왔다. 아마 2D FenwickTree로 풀면 FenwickTree안에 2중 for loop가 있기 때문에 O(M*logN*logN)이 나오지 않을까 생각한다...