문제 링크 : https://www.acmicpc.net/problem/2285
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("test.txt", "rt", stdin);
int n;
cin >> n;
long long int sumval = 0;
vector<pair<int,int>> arr(n,{0,0});
for(int i = 0; i < n; i++)
{
int x, a;
cin >> x >> a;
arr[i].first = x;
arr[i].second = a;
sumval += a;
}
sort(arr.begin(),arr.end());
long long int stand = 0;
for(int i = 0; i < n; i++)
{
stand += arr[i].second;
if(stand >= (double)sumval / 2)
{
cout << arr[i].first;
break;
}
}
return 0;
}처음에는 여러 풀이가 떠올랐던 것 같다. 우선 생각을 정리해보고 직접 해보는 게 낫겠다 싶어서 무작정 종이랑 펜으로 떠오르는 예시와 풀이를 생각해 봤는데, 잘 안 됐던 것 같다.
맨 처음에는 마을 사이 거리 * 사람 수 * 경우의 수를 모두 체크하는 방법을 떠올려 봤는데, 이미 거리 * 사람 수만 해도 10억 * 10억이라 long long으로 담을 수 있을지도 미지수고, 한 마을을 우체국으로 기준으로 둔 후 다른 마을을 모두 훑는 건 시간 복잡도 O(N^2)이므로 무조건 시간초과가 될 것 같았다.
그 다음에는 DP테이블로 해결해볼 수 있지 않을까라는 생각을 했다. 마을을 위치 기준으로 정렬한 후 i를 0~N 사이에서 움직이면서 출발지 - 도착지의 거리 쌍을 2차원 DP 테이블에 저장한 후 이 값에 감소하는 변화량이 있다면 값을 갱신할 수 없을까.. 했는데 이것도 값의 변화가 체크될 때만 의미가 있고, 시간 복잡도상으로는 사실상 똑같은 풀이인 것 같아서 빠르게 포기했다.
그런데 생각해 보니 문제에서 제시한 정답에 영향을 주는 것은 마을이 아니라 사람이 기준인 것이 문득 떠올랐고, 위의 내용에서 적어둔 변화량이 마을이 거리 기준으로 정렬되어 있고, 한 지점을 기준으로 한다면 그 기준점의 왼쪽(기준점 포함) 변화량과 오른쪽 변화량은 같다라는 생각이 문득 들었다.
예를 들자면 위치가 1,2,3,4,5...로 선형으로 쭉 이어져 있는 마을 리스트가 있고, 이 위치를 따라 우체국의 위치가 변화한다고 할 때, 우체국의 위치가 3 -> 4로 넘어갈 때에, 왼쪽 사람들의 수는 1,2,3의 인원수에서 1,2,3,4로 변경되고, 오른쪽 사람들의 수는 4,5에서 5로 변경된다. 마을 4에 있는 인원수만큼 동일하게 양쪽에 + -가 되는 것이다.
따라서 인원수의 변화가 우체국 위치 선정의 기준이 될 수도 있을 것 같다고 생각했고, 그대로 구현했더니 AC를 받았다. 증명이 영 뒷맛이 안 좋은 것 같아서 대수적으로 증명해주신 분의 블로그를 참고해서 직접 변화량에 대한 증명을 해 보았다.
https://velog.io/@its_fe/Algorithm-%EB%B0%B1%EC%A4%80-2285-%EC%9A%B0%EC%B2%B4%EA%B5%AD
이렇게 적어두고 보니 깔끔하게 증명되고 이해도 된 것 같다.
