[BOJ] 15975 : 화살표 그리기 - travelbeeee

문제 : https://www.acmicpc.net/problem/15975

---

[알고리즘풀이]

같은 색깔이면 화살표를 가장 가까운 쪽으로 그려야한다. 즉, 같은 색깔의 x 좌표 점에서는 왼쪽 혹은 오른쪽 중 가장 근접한 좌표만 선택하면 되므로 같은 색깔의 좌표별로 sorting을 한 후 화살표를 그려주면 된다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> list[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, x, y;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		list[y].push_back(x);
	}
	
	long long s = 0;
	for (int i = 1; i <= N; i++) {
		int size = list[i].size();
		if (size < 2)
			continue;
		sort(list[i].begin(), list[i].end());
		for (int j = 0; j < size; j++) {
			if (j == 0)
				s += list[i][j + 1] - list[i][j];
			else if (j == size - 1)
				s += list[i][j] - list[i][j - 1];
			else
				s += min(list[i][j + 1] - list[i][j], list[i][j] - list[i][j - 1]);
		}
	}
	cout << s;
	return 0;
}

---