합이 s일 때 만들 수 있는 최대 중앙값을 구하는 C++ 프로그램

두 개의 정수 n과 s가 주어졌다고 가정해 봅시다. 우리는 각 요소의 합이 정확히 s와 같으면서, n개의 음수가 아닌(non-negative) 요소로 이루어진 배열을 만들 때 얻을 수 있는 최대 중앙값(median)을 찾아야 합니다.

예를 들어 입력이 n = 3, s = 5라면 출력은 2가 됩니다. 배열 [1, 2, 2]의 경우 합은 5이고 중앙값은 2이기 때문입니다.

문제 해결 접근 방식

배열을 오름차순으로 정렬했을 때, 중앙값 위치부터 마지막 요소까지의 개수는 다음과 같습니다.

m := (n / 2)의 내림값 + 1

중앙값을 최대화하려면 중앙값보다 앞에 있는 요소들을 모두 0으로 만들고, 남은 합을 중앙값 이후의 요소들에 고르게 분배하는 것이 유리합니다. 중앙값 이후의 m개 요소가 모두 최소 x 이상이려면 전체 합은 최소 m × x 이상이어야 하므로, 가능한 최댓값은 다음과 같이 계산됩니다.

return (s / m)의 내림값

C++ 구현 예제

더 나은 이해를 위해 다음 구현 코드를 살펴보겠습니다.

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

int solve(int n, int s) {
    int m = n / 2 + 1;
    return s / m;
}
int main() {
    int n = 3;
    int s = 5;
    cout << solve(n, s) << endl;
}

입력

3, 5

출력

2

동작 원리 정리

n = 3, s = 5인 경우 m = 3 / 2 + 1 = 2가 되고, 반환값은 5 / 2 = 2입니다. 실제로 배열 [0, 2, 3] 또는 [1, 2, 2]처럼 합이 5이면서 중앙값이 2인 배열을 만들 수 있으며, 어떤 배치로도 중앙값을 3 이상으로 만들 수 없으므로 2가 최댓값임을 알 수 있습니다.