CS Academy - Array Removal

* CS Academy Round #9 - Array Removal

[ 분류 - DSU ]

  이 문제의 특성은 다음과 같다.

  1. 지워야하는 순서가 정해져 있다.

  2. 순서가 정해져 있는 만큼, k 번째 수를 지웠을 때 큰 수 S_k와 k+1번째 수를 지웠을 때 큰 수 S_k+1는 서로 종속적이다.

  3. 수를 제거해나가며 큰 수를 출력해야 한다.

  먼저 Greedy하게 접근해보자. S_k와 S_k+1를 비교해보자면 S_k >= S_k+1이 성립함을 직관적으로 알 수 있다. 또한 2.번에 의해 서로 종속적이기 때문에, "순서를 거꾸로" 생각하자.

  거꾸로 생각하면, 초기에 없는 데이터에서 하나씩 생성됨을 알 수 있다. 따라서 이를 DSU로 합치는 방식을 택하며, 지금 합친 것과 지금까지의 최대값을 비교해나가며 답을 "갱신"하면 된다.

  또한 거꾸로 순서를 바꾸었기 때문에 이를 리스트나 스택에 저장한 뒤, 뒤집어서 출력해주면 되시겠다.

#include <cstdio>
using ll = long long;
ll max_v(ll a, ll b){ return a > b? a : b;}
const int MAX_N = 100002;
int p[MAX_N];
long long s[MAX_N];
int find(int u){ return u == p[u] ? u : (p[u] = find(p[u]));}
void merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    p[u] = v;
    s[v] += s[u];
}
int main() {
    int N,i, q[MAX_N];
    bool used[MAX_N]={};
    long long ans[MAX_N], curans=0;
    scanf("%d",&N);
    for(i=1;i<=N;i++) {
        scanf("%d",&s[i]);
        p[i] = i;
    }
    p[0] = 0, p[N+1] = N+1;
    for(i=0;i<N;i++)
        scanf("%d",&q[i]);
    for(i=N-1;i>=0;i--) {
        used[q[i]] = 1;
        if(used[q[i]-1]) merge(q[i]-1,q[i]);
        if(used[q[i]+1]) merge(q[i]+1,q[i]);
        curans = max_v(curans, s[find(q[i])]);
        ans[i] = curans;
    }
    for(i=0;i<N;i++) printf("%lld\n",ans[i]);
    return 0;
}