백준 23830 - 제기차기

문제 링크: https://acmicpc.net/problem/23830 

23830번: 제기차기

---

문제를 요약해봅시다.

• 총 \(N\)명의 학생들 중, 점수가 \(K\) 미만인 학생의 점수를 \(q\) 더해주고, 점수가 \(K + r\) 초과인 학생의 점수를 \(p\) 빼줍니다.
• 점수 총합이 \(S\) 이상인 가장 작은 \(K\)를 찾아야 합니다. 어떤 \(K\)도 이를 만족시킬 수 없다면 \(-1\)을 출력합니다.

 

가장 먼저 점수 총합을 \(S\) 이상으로 만들 수 없는지 부터 찾아봅시다.

어떤 학생의 점수가 \(K\)보다 낮다면 그 학생의 점수는 \(q\) 증가합니다. 만약 \(K\)가 엄청나게 커서 모든 학생의 점수가 \(q\)씩 증가하게 된다면 이 때가 점수 총합이 최대가 될 것입니다.

점수 총합이 최대임에도 불구하고 점수 총합이 \(S\)보다 작다면 \(-1\)을 출력해야 되겠죠. 식으로 쓰면 다음과 같습니다.

\[\sum_{i=1}^{N}A_i+Nq < S\]

 

만약 점수 총합의 최댓값이 \(S\)보다 크다면 어떻게 해야 할까요? 곰곰이 생각해보면 이 문제는 다음과 같은 성질이 있습니다.

• \(K\)가 작아질수록 점수가 \(p\)만큼 감소하는 학생이 늘어납니다.
• \(K\)가 작아질수록 점수가 \(q\)만큼 증가하는 학생이 감소합니다.

 

이를 종합하면 \(K\)가 작아지면 점수 총합도 작아지고, \(K\)가 커지면 점수 총합도 커지는 것을 알 수 있습니다.

즉, 이분 탐색을 사용할 수 있습니다! 이분 탐색을 이용해 점수 총합이 \(S\) 이상이 되도록 하는 \(K\)의 값을 찾아봅시다.

\(K\)의 범위는 \(A_i\)의 범위를 넘어가지 않으므로, 구간 \([0, 100001]\)을 탐색하면 됩니다.

이때 \(X = 100001\)이라 하겠습니다.

 

찾는 방법은 간단합니다. 두 가지 정도를 생각해 볼 수 있습니다.

 

1)

배열 \(A\)를 미리 정렬합니다. 매 탐색마다 \(K\)보다 작은 수의 개수와, \(K + r\)보다 큰 수의 개수를 각각 구해 점수 총합을 구합니다.

배열 \(A\)가 정렬되어 있으므로 수의 개수를 구하는 것은 \(A\)에서 \(K\), \(K + r\)이 등장하는 첫 번째 위치를 각각 찾는 것과 같습니다. 따라서 시간복잡도는 \(O(\log{N})\)입니다.

이 연산을 총 \(O(\log{X})\)번 반복하고, \(A\)를 1번 정렬하므로 총 시간복잡도는 \(O(\log{X} \log{N} + N \log{N}) = O(N \log{N})\)입니다.

 

2)

이분 탐색을 매번 시행할 때마다 \(A\)를 순회하면서 점수 총합을 계산합니다. 훨씬 쉽습니다.

크기 \(N\)인 배열을 매번 순회하므로 시간복잡도는 \(O(N \log{X})\)입니다.

 

 

두 방법 모두 넉넉한 시간 안에 통과할 수 있습니다.

여기서 주의해야 할 점이 하나 있는데요, 배열의 원소 개수가 최대 \(10^5\)이고 각 원소의 값도 최대 \(10^5\)이므로 32비트 정수 자료형으로는 오버플로우가 일어날 수 있습니다.

64비트 정수형인 long long을 사용하도록 합시다.