[BOJ 23829] 백준 23829번 - 인문예술탐사주간

		SASA Programming Contest 2021 풀이
A		[BOJ 23825] SASA 모형을 만들어보자
B		[BOJ 23826] 와이파이
C1		[BOJ 23827] 수열 (Easy)
C2		[BOJ 23828] 수열 (Hard)
D		[BOJ 23829] 인문예술탐사주간
E		[BOJ 23830] 제기차기
F		[BOJ 23831] 나 퇴사임?
G		[BOJ 23832] 서로소 그래프
J1		[BOJ 23835] 어떤 우유의 배달목록 (Easy)

1. 문제

$23829$. 인문예술탐사주간 (SASA Programming Contest 2021 Open Contest D번)

백준 23829번 - 인문예술탐사주간 (https://www.acmicpc.net/problem/23829)

2. 풀이

$X$와 모든 각각의 $P(i)(1\leq i\leq N)$의 차이값(차의 절댓값)의 합을 구하는 문제이다. 질의 $Q$가 최대 $100,000$개이므로, 일일이 처리하면 시간초과가 나기 때문에 합을 미리 저장해야 한다.

절댓값을 구하는 작업이므로, $X$보다 작은 값은 $X$에서 그 값을 빼면 되고, $X$보다 큰 값은 그 값에서 $X$를 빼는 작업을 할 것이다. 따라서, $X$보다 작은 값이 $a$개이고 그들의 합이 $A$, $X$보다 큰 값이 $b$개이고 그들의 합이 $B$라면, 정답은 $(X \times a - A) + (B - X \times b)$ 이다.

정렬된 수열에서 $X$를 기준으로 작은 값, 큰 값을 나누기 위해 upper_bound를 사용하여 $X$의 위치를 찾으면 개수를 셀 수 있다. (물론 lower_bound를 써도 상관없다. 중복되는 수가 있어도 결국 계산과정에서 $0$이 되어 사라지기 때문에 문제없다.)

어떤 left~right의 합을 쉽게 계산하기 위해 미리 모든 각각의 index까지의 합을 구해 놓고 Sum[right]-Sum[left – 1]을 이용하여 구한다.

3. 채점 결과

4. 회고

코드 34~36줄의 upper_bound – 1값이 $-1$인 경우를 처리하지 않아 WA를 받았다.

5. 코드