백준 33705 (C++) 마스코트 정하기

최초 업로드: 2025-04-14 11:29:53

최근 수정 시간: 2025-07-25 09:56:45

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] 마스코트 정하기

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

## 문제 설명

$N$명의 학생들이 건국대학교의 마스코트를 투표하기 위해 모였다!

투표를 하려는 건국대학교의 학생들은 $1$번, $2$번, $\cdots$, $N$번 학생이 한 줄로 나란히 서 있다.

각 학생은 $1$과 $N$ 사이의 정수 번호를 가지는 $N$ 종류의 마스코트 후보 중 하나에게 투표하려고 한다. $i$번째 학생은 $A_i$번 후보에 투표한다.

유력 마스코트 후보인 쿠는 자신이 마스코트가 되기 위해 투표를 하려는 학생들을 쫓아내는 일을 당신에게 맡겼다.

당신은 아래의 행동을 원하는 만큼 반복할 수 있다.

<ul>
	<li>$1 \le L \le R \le N$인 두 정수 $L$, $R$을 골라 $L$번, $L + 1$번, $\cdots$, $R - 1$번, $R$번 사람 중 투표장에 남아 있는 학생들을 모두 투표장에서 내쫓는다.</li>
	<li>학생들을 내쫓은 이후, 투표장에 최소 $1$명의 학생이 남아있어야 한다. 즉, 모든 학생을 내쫓는 것은 불가능하다.</li>
	<li>투표장에서 내쫓아진 학생들은 투표에 참여할 수 없으며, 투표한 학생의 수에 포함되지 않는다.</li>
</ul>

투표한 학생이 $m$명일 때, $\left\lceil\frac{m}{2}\right\rceil$명 이상의 표를 받은 모든 후보가 마스코트가 된다.

학생들을 쫓아내는 행동을 최소 몇 번 하여야 $1$번 마스코트 후보인 쿠가 마스코트가 될 수 있을까?

## 입력

첫째 줄에 투표를 하려는 학생의 수 $N$이 주어진다. $\left(1 \le N \le 200\, 000\right)$

둘째 줄에 각 학생이 투표하려는 후보의 번호를 나타내는 $N$개의 정수 $A_1,\, A_2,\, \cdots,\, A_N$이 공백으로 구분되어 주어진다. $\left(1 \le A_i \le N\right)$

최소 한 명의 학생이 $1$번에 투표했음이 보장된다.

## 출력

$1$번 마스코트 후보인 쿠가 마스코트가 되기 위한 최소 행동 횟수를 출력한다.

## 풀이
#### 입력으로 1번 투표가 최소 1번은 들어오기에 불가능한 경우는 없다. 1번 하나만 남기면 1번이 승리하기에 최대 2번만 쫒아내면 된다. 1번만 쫒아내면 되는 경우가 있는지는 모든 범위를 다 탐색해보면 되는데 임의의 l-r 범위를 쫒아내는 것이 임의의 1-m 범위 또는 m-n 범위(1≤m≤n)를 쫒아내는 것에 포함되기에 비효율적이다. 따라서 1-m 범위 또는 m-n 범위만 쫒아내면 된다. 이 연산들은 누적합을 사용하여 최적화 할 수 있다.

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

int preSum[200001][2]; // [][1번투표, 나머지투표]

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=1;i<=n;i++) {
 int A; cin >> A;
 preSum[i][0] = preSum[i-1][0];
 preSum[i][1] = preSum[i-1][1];
 if(A==1) preSum[i][0]++;
 else preSum[i][1]++;
 }
 
 // 안 쫒아내도 되는 경우
 if(preSum[n][0]>=preSum[n][1]) {
 cout << 0;
 return 0;
 }
 
 // 한쪽만 쫒아내는 경우
 for(int i=1;i<n;i++) {
 if(preSum[i][0]>=preSum[i][1] || preSum[n][0]-preSum[i][0]>=preSum[n][1]-preSum[i][1]) {
 cout << 1;
 return 0;
 }
 }

// 양쪽을 쫒아내는 경우
 cout << 2;
}
```