백준 23858번: 중앙값 제거 C++코드(수학, 구현)

//23758

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int arr[2000002];

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=0; i<n ; i++){
        cin >> arr[i];
    }
    sort(arr, arr+n);
    int result = 0;
    for(int i=0; i<(n+1)/2; i++){
        result += int(log2(arr[i]));
    }
    cout << result+1;
    
   
}

 

문제에서 제시되는 연산을 직접 손으로 써보면서 풀면 많이 쉬워지는 문제이다. 문제를 읽자마자 캐치한 사람도 있겠지만, 제시되는 배열 중 (n+1)/2 번째에서 연산을 진행하므로, 사실 (n+1)/2 를 초과하는 인덱스는 다룰 필요가 전혀없다. 연산을 하면서 숫자들이 감소해서 0~(n+1)/2 번째 내에서 숫자가 순환하며 연산이 진행됨을 알 수 있는데, 우리가 하는 연산은 2로 나누는 것이므로 각 숫자가 몇번까지 나눠어야 0이 되는지 파악하면 된다. 결국 0~(n+1)/2 번째 인덱스의 모든 숫자에 로그2를 씌워서 나온 값을 다 더한다. 그리고 최종적으로 1을 2로 나눠 0으로 만드는 작업을 포함해 0~(n+1)/2 번째 인덱스의 모든 숫자에 로그2를 씌워서 나온 값 + 1이 이 문제의 답이 된다.

 

참고로 입력되는 값이 많아서 빠른 입출력을 사용해야한다.