[BOJ] 백준 22345. 누적 거리 (Gold III)

KOI 2차대회 중등부 문제이다.

예상보다 꽤나 고전했던 문제.

문제는 아래와 같다.

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

22345번: 누적 거리

---

의식의 흐름 및 해설

범위가 상당히 크기 때문에 좌표 범위대로 스위핑은 불가능하다.

대신, N개의 좌표를 순서대로 스위핑은 가능하며, 주어진 q가 어느 마을 사이에 있는지 이분탐색으로 구해줄 수 있겠다.

이렇게 대충 O(QlgN) 시간복잡도를 떠올릴 수 있는데,

문제는 누적거리가 어떻게 되는지이다.

 

누적합으로 구하는 건 맞을 듯한데, q가 어디인지에 따라 너무 헷갈려서 식을 세워보기로 했다.

여기서 식을 세우길 정말 잘한게, q의 위치에 따라 식이 달라지기 때문에 식을 세우지 않고 한눈에 파악하기가 굉장히 힘들다.

 

우리가 구하려는 식을 정리하면 아래와 같다.

qi는 쿼리에서 q로 주어지므로 이 식에선 변수가 아니다.

idx는 이분탐색 lower_bound로 찾아준다.

 

즉, 여기서 필요한 것은 인원수의 누적합, 그리고 인원수*거리의 누적합이 필요하다.

이 때, 순서대로 정렬해주는 것, 잊지 말자.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 200011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const ll MOD = 1e9 + 7;
ll N, Q, p[MAX], cnt[MAX], d[MAX];
vector<ll> a;
vector<pl> v;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		ll n, cost;
		cin >> n >> cost;
		a.push_back(cost);
		v.push_back({ cost, n });
	}
	sort(all(a));
	sort(all(v));
	for (int i = 1; i <= N; i++) {
		p[i] = p[i - 1] + v[i - 1].first;
		d[i] = d[i - 1] + v[i - 1].first * v[i - 1].second;
		cnt[i] = cnt[i - 1] + v[i - 1].second;
	}
	while (Q--) {
		ll n;
		cin >> n;
		ll idx = lower_bound(all(a), n) - a.begin();
		cout << d[N]-2*d[idx]-(n*(cnt[N]-2*cnt[idx])) << "\n";
	}
}

누적합은 1~N까지, 그리고 idx는 0~N-1까지로 찾기 때문에 누적합을 빼줄 때, idx-1이 아닌 idx를 빼준다.

---

어떤 알고리즘을 써야할지는 쉽게 보였지만,

식을 세우기 전까진 꽤나 고생했던 문제.

식이 복잡하거나, 특정 위치로 인한 절댓값 케이스로 분류된다면 식을 간단히 할 수 있지 않은지 확인하는 습관이 중요할 듯하다.

 

근데 이후에 다른 사람들 풀이를 보니, 식 세우지 않고 케이스분류를 통해 풀거나, 다른 방법으로 푼 사람들도 좀 보이는 듯하다.