[S2] 백준 14400번 편의점 2 C++ 수학, 정렬

리뷰

 

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

맨허튼 거리 합 최소를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• xs, ys : x, y좌표를 저장할 배열
• n : 좌표의 개수를 저장할 변

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 좌표를 입력 받아 xs, ys배열을 초기화한다.
2. sort함수를 통해 xs, ys배열을 오름차순으로 정렬한다.
3. 변수 sum을 0으로 초기화 하고, 변수 mx, my를 각 배열의 중앙값으로 저장한다.
4. n개의 좌표를 순회하며 mx와 각 x좌표의 거리와 my의 각 y좌표의 거리의 합을 sum에 더해준다.
5. sum에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

없음

 

 

정답 코드

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

const int N = 1e5;
int xs[N], ys[N];
int n;

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, y; cin >> x >> y;
		xs[i] = x, ys[i] = y;
	}

	sort(xs, xs + n);
	sort(ys, ys + n);

	long long sum = 0;
	int mx = xs[n / 2], my = ys[n / 2];
	for (int i = 0; i < n; ++i) sum += abs(mx - xs[i]) + abs(my - ys[i]);
	cout << sum;
}