백준 30471 (C++) 호반우가 학교에 지각한 이유 4

최초 업로드: 2025-10-10 13:49:03

최근 수정 시간: 2025-10-10 13:49:03

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 호반우가 학교에 지각한 이유 4

[문제 링크](https://www.acmicpc.net/problem/30471)

## 문제 설명

사실 호반우가 이세계에 도착했을 때부터 호반우의 이세계 모험은 생방송 플랫폼인 트위치를 통해 지구에서 방송되고 있었다.

현재 방송 화면에는 호반우가 $N$마리의 킹 슬라임이 있는 던전을 탐험하려는 모습이 송출되고 있다. 모든 킹 슬라임은 서로 다른 슬라임 그룹에 속해있으며, $1$번부터 $N$번까지 번호가 주어져 있다.

방송의 유일한 시청자인 상호는 TWIP의 슬롯머신을 $M$번 사용해 호반우가 던전을 탐험하기 전에 슬라임 그룹을 합쳐보려고 한다.

슬롯머신을 돌리면 $1 \le a

인벤토리에서 $a,\,b$가 적힌 아이템을 소비하여 $a$번 킹 슬라임이 속한 그룹과 $b$번 킹 슬라임이 속한 그룹을 합칠 수 있는데 이때 이미 $a$번 킹 슬라임과 $b$번 킹 슬라임이 같은 슬라임 그룹에 속해있다면 합쳐지지 않는다. 두 슬라임 그룹이 합쳐지게 되면 $($합쳐진 슬라임 그룹에 속한 킹 슬라임의 마릿수$-1)$마리의 미니 슬라임을 만든다.

상호는 슬롯머신을 돌린 횟수에 따라 던전에 슬라임들(킹 슬라임과 미니 슬라임)을 얼마나 많이 만들 수 있을지 궁금해졌다. 스트리머로서 유일한 시청자인 상호에게 답을 알려주자.

## 입력

첫 번째 줄에 슬라임의 수 $N$과 슬롯머신을 돌린 횟수인 $M$이 공백을 두고 주어진다. $(2 \le N \le 200\,000,\,1 \le M \le 300\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 슬롯머신을 돌려 나온 아이템에 적힌 양의 정수 쌍 $a,\,b$가 순서대로 공백을 두고 주어진다. $(1 \le a

## 출력

$M$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 슬롯머신을 $i$번까지 돌려서 얻은 아이템들을 사용했을 때 던전에 있을 수 있는 슬라임들의 마릿수 중 최댓값을 출력한다.

## 풀이
최적은 그룹에 슬라임 한 마리씩 추가하는 것이고, 이렇게 추가할 때 미니 슬라임이 (size-1)size/2 마리씩 증가한다. 이를 분리 집합으로 구현하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll total, parent[200'000], _size[200'000];

int _find(int x) {
    if(x==parent[x]) return x;
    return parent[x] = _find(parent[x]);
}

void _union(int x, int y) {
 x = _find(x);
 y = _find(y);
 if(x==y) return;
 if(x<y) parent[y]=x;
 else parent[x]=y;
 total -= (_size[x]-1)*_size[x]/2 + (_size[y]-1)*_size[y]/2;
 _size[x] = _size[y] = _size[x]+_size[y];
 total += (_size[x]-1)*_size[x]/2;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 for(int i=0;i<n;i++) {
 parent[i]=i;
 _size[i]=1;
 }

total=n;
 while(m--) {
 int a, b; cin >> a >> b;
 _union(a-1, b-1);
 cout << total << '\n';
 }
}
```