[1280] 나무 심기

https://www.acmicpc.net/problem/1280

1280번: 나무 심기

세그먼트 트리 문제다.

 

풀이

i번째 나무의 좌표 A에 대한 비용은 다음과 같이 정리가 가능하다. 

|(A -[i-1] 번 나무 좌표)| + |(A - [i-2] 번 나무좌표)| +... + |(A - [i-i] 번 나무 좌표)|
->  | A*i - ([i-1]번 나무 좌표 + [i-2] 번 나무좌표 +... + [i-i] 번 나무좌표) |

즉 해당 부분을 여태 심어진 나무의 갯수와 좌표의 누적값을 통해 계산이 가능하다는 것이다. 따라서 0부터 199,999 좌표의 나무개수와 해당 구간의 누적 좌표값을 표현하는 세그먼트 트리를 생성하여 다음과 같이 계산이 가능해진다.

좌측 비용 = (A보다 좌측에 있는 나무의 갯수 * A) - (A보다 좌측 좌표에 심어진 나무의 거리(좌표) 총합)
우측 비용 = ((A보다 우측 좌표에 심어진 나무의 거리(좌표) 총합) - (A보다 우측에 있는 나무의 개수 * A)
A좌표에 나무를 심는 비용 = 좌측비용 + 우측비용

매 입력마다 해당 좌표의 비용을 구하여 계산한 뒤, 다음 나무의 비용 계산을 위해 나무의 갯수를 갱신해 주면 값을 구할 수 있다.

 

정답 코드

세그먼트 트리의 활용은 정말 다양한 것 같다.