크기가 n인 배열 A가 있다고 가정해 봅시다. 한 학교에 학생이 n명 있으며, 각 학생은 정확히 k개의 표를 가지고 있고 모든 표를 반드시 사용해야 합니다. 후보 정당은 두 개입니다. 배열의 값 A[i]는 i번째 학생이 첫 번째 정당에게 A[i]만큼의 표를 던졌다는 의미이며, 그렇다면 두 번째 정당은 자동으로 k - A[i]개의 표를 받게 됩니다.
여기서 두 번째 정당이 선거에서 승리할 수 있도록 k를 설정하려고 합니다. 이때 가능한 k의 최솟값은 얼마일까요?
예를 들어 입력이 A = [2, 2, 3, 2, 2]라고 해 보겠습니다. 첫 번째 정당은 2 + 2 + 3 + 2 + 2 = 11표를 받게 됩니다. 만약 k = 5라면 두 번째 정당은 3 + 3 + 2 + 3 + 3 = 14표를 받아 선거에서 승리하게 됩니다. 따라서 출력은 5입니다.
문제 해결 접근 방식
이 문제를 해결하기 위해서는 두 가지 조건을 고려해야 합니다.
1. 승리 조건
첫 번째 정당이 받는 총 표 수는 배열의 합 s입니다. 두 번째 정당이 받는 총 표 수는 전체 표에서 첫 번째 정당의 몫을 뺀 n × k - s입니다. 두 번째 정당이 이기려면 다음 부등식이 성립해야 합니다.
n * k - s > s → k > 2 * s / n
따라서 승리를 보장하는 최소 정수 k는 ⌊2s / n⌋ + 1입니다.
2. 표 수 제약 조건
각 학생은 자신이 가진 표보다 많은 표를 한 정당에 줄 수 없으므로, k는 배열 내 최댓값 m보다 작을 수 없습니다. 즉, k ≥ m이어야 합니다.
결국 답은 두 조건 중 더 큰 값, 즉 max(m, 2 * s / n + 1)이 됩니다.
알고리즘 단계
위 내용을 바탕으로 다음 단계를 따릅니다.
n := A의 크기
k := 0으로 초기화하고, k < n인 동안 반복(k를 1씩 증가):
x := A[k]
m := m과 x 중 최댓값
s := s + x
m과 (2 * s / n + 1) 중 최댓값 반환C++ 구현 예제
더 나은 이해를 위해 다음 구현 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size(), k = 0, s = 0, m = 0;
for (int k = 0; k < n; k++){
int x = A[k];
m = max(m, x);
s += x;
}
return max(m, 2 * s / n + 1);
}
int main(){
vector<int> A = { 2, 2, 3, 2, 2 };
cout << solve(A) << endl;
}입력
{ 2, 2, 3, 2, 2 }출력
5
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.