[백준] 7571_점 모으기_C++ 풀이, 시간초과 해결하기

 

백준 점 모으기 문제링크

www.acmicpc.net/problem/7571

7571번: 점 모으기

 

완전탐색으로 빠르게 풀면서도 뭔가 의심스러웠다... 이렇게 간단하다고..?

역시나ㅎ 시간초과였다. 찾아보니 중간값으로 해결해야 한다는데 그 이유를 기록하고자 한다,

 

먼저, 완전탐색으로 푼 시간 초과 코드는 아래와 같다.

 

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

int n, m, ans;
vector<pair<int, int>>v;
void init() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		v.push_back(make_pair(x, y));
	}
	ans = n + n;
}

int getDistance(int x, int y) {
	int d =0;
	for (pair<int, int> p : v) {
		d += abs(p.first - x) + abs(p.second - y);
	}
	return d;
}

int main() {

	init();
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int d = getDistance(i, j);
			ans = min(d, ans);
		}
	}
	cout << ans;
}

 

시간 초과라길래 나름대로.. if문을 넣어서 현 ans보다 크면 break를 하는 등(택도 없는 조건ㅋㅋㅋ) 끄적여봤지만..

중간값을 사용해서 푸는 것이 정답이었다.

 

 

왜?

쉽게 이해하기 위해 x, y중 하나만 따질 수 있도록 상황을 가저해보자. 모든 m개의 점이 한 줄에 적혀 있는, 즉 한 행에 열번호만 다르게 위치한다고 가정하자. 

 

 

위 그림처럼 1행 위에 모든 점이 있다면 모일 위치 (p,q)는 (p, 1)로 맨 윗줄의 한 점일 것이다.

따라서 x좌표만 고려한다면 식은 |p - 1| + |p-4| + |p-11|이고, 이 값이 최소가 되는 p를 구해서 그때의 최솟값을 구해야 한다.

 

어릴 때 배운 것을 생각해서 그래프를 그리면, 경우에 따라 나눠서 그리게 된다.

 

 

그래프를 보면 중간값인 4일 때 거리가 최소가 된다.

따라서 각 x좌표와 y좌표를 정렬해서 각각의 중간값과 거리를 구하면 x도 최소, y도 최소가 되니 최종적으로 최솟값을 구할 수 있다.

 

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

int n, m, ans;
int mx, my;
int ax[100000]; int ay[100000];
void init() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> ax[i] >> ay[i];
	}
	sort(ax, ax + m);
	sort(ay, ay + m);
	mx = ax[m / 2];
	my = ay[m / 2];
}

int main() {

	init();
	for (int i = 0; i < m; i++) {
		ans += abs(mx - ax[i]) + abs(my - ay[i]);
	}
	cout << ans;
}