- 모든 경로를 계산하는 방법을 이용
- 하나의 점에서 다른 모든 점들까지의 거리를 구하고 가장 짧은 거리이면 답을 갱신해주는 방식
- O(n^2)밖에 안되지만 Timeout이 나버린다...
- left를 0으로 잡아서 아직 1명도 없는 경우이고
- right는 모든 인구수의 총합이다.
- 여기서 right/2에 가까운 위치를 찾는 코드
- 이유는 아직 잘 모르겠다...
#include<iostream>
#include<vector>
#include<utility>
#include<limits.h>
#include<stdlib.h>
using namespace std;
int chooseCity(int n, vector<pair<int,int>> city)
{
int answer = -1;
long shortest_dist = LONG_MAX;
// O(n^2)
for(int i=0; i<city.size(); i++){
long dist = 0;
for(int j=0; j<city.size(); j++){
if(i==j) continue;
dist += abs(city[i].first - city[j].first) * city[j].second;
}
if(dist < shortest_dist){
shortest_dist = dist;
answer = city[i].first;
}
}
return answer;
}
int main()
{
int tn = 3;
pair<int,int> a,b,c;
a.first = 1, a.second = 5;
b.first = 2, b.second = 2;
c.first = 3, c.second = 3;
vector<pair<int,int>> tcity{a,b,c};
//아래는 테스트 출력을 위한 코드입니다.
cout<<chooseCity(tn,tcity);
}
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<limits.h>
using namespace std;
int chooseCity(int n, vector<pair<int,int>> city)
{
int answer = 0;
int i=0;
// 거리의 좌표를 제일 작은것부터 큰것까지 순서로 일직선 상에 늘어놓은 후에
sort(city.begin(), city.end());
// 제일 왼쪽을 0 오른쪽을 총 사람의 인구수로 정의하고
long long left = 0;
long long right = 0;
for(int i=0; i<n; i++){
right += city[i].second;
}
// 과정이 사람수가 중간일 부분을 찾는거 ... 이유는 잘 모르겠다..
long long half_right = right * 0.5f;
for(i=0; i<n; i++){
left += city[i].second;
if(left >= half_right){
answer = city[i].first;
break;
}
}
return answer;
}
int main()
{
int tn = 3;
pair<int,int> a,b,c;
a.first = 1, a.second = 5;
b.first = 2, b.second = 2;
c.first = 3, c.second = 3;
vector<pair<int,int>> tcity{a,b,c};
//아래는 테스트 출력을 위한 코드입니다.
cout<<chooseCity(tn,tcity);
}
- 솔직히 이 문제는 아직도 이해가 안간다... 수학적으로 어떤게 이용된지모르곘고 일직선상에서 거리도 제 각각이고 그에 따른 수도 다른데 왜 사람들 수의 평균인 위치를 찾으면 그게 제일 최단거리인 장소일까?...
- 인구수의 평균 부분이 왜 최단거리이지?...