BOJ 1280 나무 심기

1번부터 N번까지의 나무가 있는데, 각 나무를 어디에 심을지가 주어진다.
1번 나무부터 시작해서 차례대로 N번 나무까지 심을 것이고 1번 나무를 제외한 모든 나무는 심는데 비용이 든다. 각 나무를 심는데 드는 비용은 각 나무에서 현재 심어져 있는 모든 나무까지의 거리의 합이다.
이 때, 2번 나무부터 N번 나무까지 각 나무를 심는데 드는 비용의 곱을 구하는 문제이다.
데이터가 최대 20만개가 들어오기 때문에, 각 나무를 심는데 드는 비용을 일일이 계산하면 O(n제곱)의 시간이 걸릴 것이다.

각 나무를 심는데 드는 비용을 그려보면, 그리 어렵지 않다.
d[n] : n번째 나무를 심는데 드는 비용 이라고 하자.
그리고 그림을 그려서 보면, d[n]은 d[n-1]를 구성하는 n-1번째 이전의 나무들과의 거리에 각각 pos[n]-pos[n-1]을 더한값과, pos[n]-pos[n-1]으로 구성돼있는 것을 볼 수 있다.

즉, d[n] = d[n-1] + (pos[n]-pos[n-1])*(n-1) 이 된다.
한 번 풀어봐야겠다. 계속 틀려서 이것 저것 해보다가 떠오른 것이, 나는 n번 나무가 n-1번나무보다 죄표상으로 앞에 온다고 가정하고 풀고 있었다... 문제에는 n번 나무가 무조건 n-1번 나무 보다 좌표상 뒤의 위치에 온다는 말이 없다. 아... 다시 처음부터 생각해 봐야겠다.

어렵다... 질문 게시판과, 구글 검색을 해보니 segment tree나 fenwick tree를 써서 풀 수 있는 것 같다. fenwick tree를 어떻게 이용할지, 무엇을 저장하면 좋을지 생각해 봐야겠다.
결국 kks227님의 블로그의 풀이를 읽어봤다. 감탄했고 동시에 난 접근도 못했다는 생각에 많이 반성했다. 정말 열심히 하자.

먼저 알게된 것은 문제에 한 위치에 나무가 한 그루만 세워진다는 말이 없으므로 한 위치에 나무가 여러 그루 세워질 수 있다.
펜윅 트리를 어떻게 활용하냐면, 일단, 펜윅트리를 처음에 업데이트 해줄 때, 0부터 x까지의 거리로 업데이트 해준다. 즉, 펜윅트리에서 쿼리x가 의미하는 것은 좌표 x이하의 좌표들에 대해서 좌표 0부터의 거리들의 합이된다. 간단히 말하면 그냥 좌표 x이하의 좌표들의 합이되는데, 좌표 0부터 각 좌표까지의 거리의 합으로 생각하는 것이 뒤에 나오는 것을 이해하기 좋다.
그리고 펜윅 트리가 하나 더 있어야 한다. 각 좌표에 대해 각 좌표까지의 존재하는 나무의 개수를 기록해야 한다. - cnt_query라고 하겠다.

자, 이제 어떻게 구할 것이냐, 일단 n번째 나무가 들어왔다고 치자. 그럼 n번째 나무 이전의 나무들은 왼쪽에 있을 수도, n번재 나무의 위치에 있을 수도, 오른쪽에 있을 수도 있다.

먼저 n번째 나무의 위치 이하에 해당하는 이전 나무들에 대해서 거리의 합을 구해보자.
결론부터 말하면 cnt_query(pos[n]) * pos[n] - query(pos[n]) 이 될 것이다.
일단 쉽게 이해하기 위해 pos[n]이하의 위치에 1부터 n번 나무까지 모두 있다고 가정해보자. 일단 n번나무에서 1, 2, 3..., n-1, n번째 나무까지의 거리들의 합은
(pos[n]-pos[1]) + (pos[n]-pos[2])+..+(pos[n]-pos[n-1])+(pos[n]-pos[n]) 으로 표현할 수 있고, 정리하면
pos[n] * n - (pos[1]+pos[2]+...+pos[n]) 이 된다.
query(pos[n])은 0부터 1, 2, ...n까지의 거리의 합으로서 (pos[1]+pos[2]+...+pos[n])에 해당하고, cnt_query(pos[n]) * pos[n]이 pos[n] * n에 해당한다.

알고보면 별거 아닌 것 같지만 난 조금이라도 비슷하게 생각조차.. 아니 접근조차 못했다.
갑자기 드는 생각인데, 처음부터 펜윅트리로 어떻게 하지가 아니라, 이렇게 식을 세워보고 펜윅트리를 써야겠구나...하면 나을 것 같은데... 음 그것도 쉬운 건 아니려나...정말 열심히 해야겠다. 문제를 많이 풀어보라는 말이 괜히 있는 게 아닌 것 같다.

자 n번째 나무의 위치보다 이제 오른쪽에 있는 나무들에 대해서 거리의 합을 구해보자.
결론부터 말하면
query(pos[rightEnd]) - query(pos[n]) - (n - cnt_query(pos[n]) * pos[n]
오른쪽에 나무가 어디까지 있는지 모르지만 그냥 범위에서 제일 끝에 해당하는 pos[rightEnd]에 대해서 query를 해주면 0부터 모든 나무들까지의 합을 구할 수 있다. 이제 이 모든 나무들까지의 거리의 합에서 query(pos[n])을 빼주면 n보다 오른쪽에 있는 나무들의 거리의 합만 남는다 (그냥 n번째 나무의 위치보다 오른쪽에 있는 나무들의 거리의 합이라고 보면 된다). 여기서 오른쪽에 있는 나무들의 개수만큼 pos[n]을 빼주면 pos[n]에서 오른쪽에 있는 나무들까지의 거리의 합이 될 것이다.

자 이제 구현해보자.
시간 초과를 받는다. 전혀 시간 복잡도 상으로 문제가 없는데...
그래서 랜덤으로 데이터를 생성해서 돌려보는데... 바로 시간 초과다.. 분석해보니 데이터 중에 위치값이 0이 들어오는 곳에서 멈춘다. 각각의 좌표는 0이상 200000이하... 아...
펜윅트리는 인덱스를 1부터 사용하는데, 0이 들어올 경우 업데이트 해줄 때 무한루프에 빠진다. 이 부분은 전혀 생각 못했었다....그래도 정말 감사하게도 바로 원인을 찾을 수 있었다. 그렇다면 펜윅트리의 크기를 1늘리고 들어오는 위치값에 1씩 더해서 사용해야겠다.
결국 AC를 받았다.
열심히, 간절하게, 몰두해서 하자.

참고 및 출처 : kks227님 블로그