문제

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

풀이

• 이중 벡터 이용 //point[i] : 색깔 i인 점의 좌표들
• 정렬 --> 점을 좌표순으로 재배열하기
• 거리 중 어떤 걸 더해야 하는지 생각해서, 하나씩 더해준다.
  • 제일 왼쪽, 제일 오른쪽은 따로 더하고
  • 나머지 화살표의 거리: 그 점에서 바로 왼쪽 옆 점까지의 거리(left변수), 바로 오른쪽 옆 점까지의 거리(right변수) 중 더 작은 값.

어려웠던 점

• 점의 좌표, 개수, 색깔 등은 범위가 int로 커버되는데,
  좌표의 합인 sum은 long long으로 해야 한다. (처음에 int로 해서 서브테스크 2,3,4를 틀렸다.)
• 제일 왼쪽 화살표(p0에서 p1로 가는 것)의 거리,
  제일 오른쪽 화살표의 거리를 따로 더해주어야 했는데, 처음엔 놓쳤다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;
	vector<vector<int>> point(N + 1); //point[i] : 색깔 i인 점의 좌표들

	/*점 정보 입력받기*/
	int x, y;
	for (int n = 0; n < N; n++) { //N번 반복
		cin >> x >> y; //좌표 x, 색깔 y
		point[y].push_back(x);
	}

	/*정렬하기, 화살표 거리 합 구하기*/
	long long sum = 0;
	int left, right, J;
	for (int i = 1; i <= N; i++) {
		J = point[i].size();
		if (J == 0 || J == 1)
			continue; //1이면 sum += 0이므로.

		sort(point[i].begin(), point[i].end());
		sum += point[i][1] - point[i][0];
		sum += point[i][J - 1] - point[i][J - 2];
		for (int j = 2; j < J; j++) {
			right = point[i][j] - point[i][j - 1];
			left = point[i][j - 1] - point[i][j - 2];
			sum += min(right, left);
		}
	}

	cout << sum;

	return 0;
}