[G4] 백준 23829번 인문예술탐사주간 C++ 정렬, 누적합, 이분 탐색

리뷰

 

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

쿼리로 주어진 위치에서 각 나무와의 거리 합을 구하는 문제

 

 

전역 변수

1. N : 배열의 최대 크기를 정의할 상수 변수
2. arr : 나무 위치 정보를 저장할 배열
3. pre_sum : 나무 위치 누적합을 저장할 배열
4. n : 나무의 개수를 저장할 변수
5. q : 쿼리의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, q값을 입력 받고, n개의 나무 위치를 입력 받아 arr배열을 초기화한다.
2. sort함수를 통해 arr배열을 오름차순으로 정렬한다.
3. n개의 나무 위치를 순회하며 pre_sum배열에 누적합 데이터를 초기화한다.
4. q번의 while루프를 통해 매 쿼리 마다 변수 x에 사진을 찍을 위치를 입력 받는다.
5. 변수 idx에 lower_bound함수를 통해 arr배열에서 값이 x이상인 인덱스를 저장한다.
6. 변수 L_sum에 idx가 0일 경우 0, 아닐 경우 pre_sum[idx-1]값을 저장한다.
7. 변수 R_sum에 pre_sum[n-1] - L_sum값을 저장한다.
8. 변수 L에 x*idx에서 L_sum을 뺀 값을 저장한다.
9. 변수 R에 R_sum에서 x*(n-idx)를 뺀 값을 저장한다.
10. L+R을 출력 후 개행문자를 삽입하여 줄바꿈을 수행해 준다.
11. 모든 쿼리를 수행할때까지 위 로직을 반복한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. idx가 0일경우 OOB에러를 반환할 수 있으므로 삼항 연산을 통해 잘못된 인덱스를 참조하지 않도록 해주었다.
2. int범위 오버플로우가 발생할 수 있으므로 long long타입을 사용해주었다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;
using ll = long long;

const int N = 1e5;
int arr[N];
ll pre_sum[N];
int n, q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;
		arr[i] = x;
	}
	sort(arr, arr + n);
	for (int i = 0; i < n; ++i) pre_sum[i] = i == 0 ? arr[i] : pre_sum[i - 1] + arr[i];

	while (q--) {
		int x; cin >> x;

		int idx = lower_bound(arr, arr + n, x) - arr;
		ll L_sum = idx == 0 ? 0 : pre_sum[idx - 1];
		ll R_sum = pre_sum[n - 1] - L_sum;

		ll L = 1ll * x * idx - L_sum;
		ll R = R_sum - 1ll * x * (n - idx);		
		cout << L + R << "\n";
	}
}