[C++] 33118번 ICPC Provincial

https://www.acmicpc.net/problem/33118

---

 

25/01/05

 

 

간단한 그리디 문제다. 이전에 해결했던 물정 수열과 비슷한 느낌을 받았다.

---

 

문제 접근 방식:

 

 

2025.01.04 - [알고리즘/백준 문제 풀이] - [C++] 26648번 물정수열

[C++] 26648번 물정수열

이것도 중앙값에 대한 관찰을 해야하는 문제였다. 핵심 관찰은 중앙값을 조절해야 한다는 점이었다.

 

여기 문제는 길이 $3N$의 수열이 주어질 때 이 수열을 크기 $3$짜리 수열로 다 쪼개고, 그것의 중앙값들의 최솟값이 최대가 되도록 만드는 것이다.

 

수열 $A = [a_1, a_2, \dots, a_{3N}]$가 정렬을 한 상태라고 하면, 어떤 팀의 중앙값은 최소 $a_2$에서 최대 $a_{3N-1}$이 될 수 있다.

 

결국 중앙값들의 최솟값이 최대가 되게 만들려면 중앙값이 될 수 있는 하한을 최대로 올려야 한다.

 

예를 들어 첫번째 팀을 구성할 때 $a_1, a_{3N}$까지만 뽑고 나머지 한 명을 뽑는 방식으로 해보자.

 

이후 두번째 팀은 $a_2, a_{3N-1}$까지만 뽑으면 나머지 한명은 $a_3$부터 시작하므로, 그렇게 하한을 계속 올릴 수 있다.

 

그렇게 $N$번째 팀은 $a_{N}, $a_{2N+1}$까지만 뽑는다고 해보자.

 

이제 나머지 한 명을 각 팀에 임의로 배정하게 된다면, 결국 중앙값들의 범위는 $a_{N+1}$부터 $a_{2N}$까지가 되므로 중앙값의 최솟값은 $a_{N+1}$이 된다.

 

즉, 위에처럼 팀을 구성할 때 3그룹으로 분류하고, 1그룹은 $a_1$부터 $a_N$, 2그룹은 $a_{N+1}$부터 $a_{2N}$, 3그룹은 $a_{2N+1}$부터 $a_{3N}$으로 정한다.

 

이후 각 그룹에서 한 명씩 뽑아서 팀을 구성한다면 중앙값들은 항상 2그룹에 속하게 되므로, 그 그룹의 최솟값인 $a_{N+1}$이 답이 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 33118번 ICPC Provincial
// 그리디, 정렬
/*
접근 방법:
뭔가 물정 수열 비슷한 느낌 남
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

int main(void){
    fastio;
    int N, a; cin >> N;
    vector<int> A;
    for (int i = 0; i<3*N; i++){
        cin >> a; A.push_back(a);
    }
    sort(A.begin(), A.end());
    cout << A[N];
    return 0;
}