https://www.acmicpc.net/problem/1280
1280번: 나무 심기
첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다.
www.acmicpc.net
세그먼트 트리 문제다.
풀이
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좌표에 나무를 심는 비용 = 좌측비용 + 우측비용
매 입력마다 해당 좌표의 비용을 구하여 계산한 뒤, 다음 나무의 비용 계산을 위해 나무의 갯수를 갱신해 주면 값을 구할 수 있다.
정답 코드
세그먼트 트리의 활용은 정말 다양한 것 같다.
'Problem Solving > BOJ' 카테고리의 다른 글
| [3653] 영화 수집 (0) | 2023.03.12 |
|---|---|
| [7578] 공장 (0) | 2023.03.11 |
| [1725] 히스토그램 (0) | 2023.03.07 |
| [1849] 순열 (0) | 2023.03.05 |
| [1517] 버블 소트 (0) | 2023.03.02 |