BAEKJOON 9027번: Stadium

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

9027번: Stadium

문제가 영어로 되어 있으므로 문제에 대한 간단한 설명을 하겠다.

 

$$ \sum_{i=1}^N \left| x-x_i \right|    - (1) $$

 

주어진 x값 중 위의 값을 가장 작게 만드는 x값을 찾는 문제를 많이 접해보았을것이라고 생각한다.

이 값들에 가중치가 생겼다고 생각하면 현재 풀려고하는 문제가 된다.

식으로 나타내면 아래와 같다.

 

$$ \sum_{i=1}^{N} w_i×\left| x-x_i \right|    - (2) $$

 

가중치가 없는 문제에서는 주어진 x값들의 중앙값이 정답이 되지만 이 문제에서는 그렇지 않다.

가중치를 고려해 주어야하는데 이를 무식하게 어떤 한 점에대해서 모든 점들을 상대로 계산할 경우 시간복잠도는 O(N^2) 이다. 문제에서 N이 100000까지 커질 수 있으므로 다른 방법을 찾아야 한다.

 

x값들이 오름차순 정렬이 되어 있는 상태에서 x값을 하나씩 올려가며 진행할 때의 식 (2)의 변화량에 초점을 맞추어보자.

식 (2)의 변화량은 아래와 같다. 

 

$$ \sum_{j=1}^{i} w_i - \sum_{j=i}^{N} w_i $$

 

이 값은 부분합을 이용하여 간단히 계산할 수 있으며, 부분합을 이용할 시 위는 아래와 같이 나타낼 수 있다.

(S_n은 1~n까지의 가중치의 합이다.)

 

 

$$ 2×S_{i-1}-S_{N} $$

 

이로서 첫 번째 점을 제외한 다른 모든 점들에서 계산을 상수시간에 처리할 수 있으므로 전체 시간 복잡도는 O(N)이다.

 

아래에 정답코드를 첨부하겠다.

 

 

#include <cstdio>
typedef long long ll;
const int R=1e5+3;
ll w[R],S[R],X[R],mn,now;
int main(){
    int T,N,i,ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);ans=X[1],mn=0;
        for(i=1;i<=N;i++)scanf("%lld",&X[i]);
        for(i=1;i<=N;i++){scanf("%lld",&w[i]);S[i]=w[i]+S[i-1];}
        for(i=1;i<=N;i++)mn+=(X[i]-X[1])*w[i];
        for(i=2;i<=N;i++){
            now=mn+(S[i-1]*2-S[N])*(X[i]-X[i-1]);
            if(mn>now){
                mn=now;
                ans=X[i];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}