백준 20929: 중간

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

20929번: 중간

 

풀이

우선 N=1일 때는 A의 1번째 원소, B의 1번째 원소를 질문하여 그 중 작은 값을 출력하여 끝내면 됩니다.

 

질문의 한계인 40은 2×19+2라는 것을 관찰할 수 있습니다. 그러므로 A와 B를 각각 logN+1번씩 질문하면 될 것입니다.

A 배열에서 중앙값이 존재한다고 판단되는 범위를 la번부터 ra번까지, B 배열에서 마찬가지로 lb번부터 rb번까지라고 해봅시다. 초기값은 la=lb=1, ra=rb=N이 되겠죠. 

la부터 ra번에서의 중앙값을 p라고 합시다(그렇다면 p는 A의 (la+lb)/2번째 수가 됩니다). 같은 방법으로 q를 B의 lb부터 rb번에서의 중앙값이라고 잡습니다.

그리고 la부터 ra까지의 길이를 x, lb부터 rb까지의 길이를 y라고 잡습니다(A와 B를 합친 배열의 중앙값은 두 개의 부분 배열의 중앙값과 같고, 부분 배열들을 합친 배열(S라고 합시다)의 (x+y)/2번째 수가 됩니다).

질문 두 번을 써서 p와 q를 질문합니다. 그리고 p와 q를 비교하여 다음과 같이 씁니다(일반성을 잃지 않고 $p\geq q$라 하겠습니다).

 

첫 번째, $p>q$일 때 S에서 q보다 확정적으로 큰 값은 A의 부분 배열에서 p 이상의 값, B의 부분 배열에서 q보다 큰 값이 있습니다. 그렇다면 q는 S를 오름차순 정렬했을 때 최대 x/2+y/2-1번째까지 나올 수 있습니다. 그러므로 B의 부분 배열에서 q 이하의 원소는 무시해버리면 됩니다(lb=(lb+rb)/2+1).

똑같이 A에서도 S에서 p는 최소 x/2+y/2번째까지 나올 수 있으므로 A에서 p보다 오른쪽에 나오는 원소는 무시하면 됩니다(ra=(la+ra)/2).

예를 들어서 설명해봅시다.

A	1	3	5(=p)	7	9	11
B	2	4(=q)	6	8

위와 같은 배열이 있을 때, S에서 q보다 큰 수는 총 6개입니다. 따라서 S에서 4는 4번째 위치에 있게 되고 S는 길이가 10이므로 중앙값이 될 수 없게 됩니다. 따라서 B의 원소인 2와 4를 무시할 수 있습니다.

S에서 5는 5번째의 위치에 있게 됩니다. 그러므로 5 오른쪽의 7, 8, 9는 무시할 수 있습니다.

A	1	3(=p)	5
B	6(=q)	8

3과 6을 비교하니 6이 더 큽니다. 따라서 6보다 큰 원소인 8을 무시하고, 3 이하의 원소인 1, 3을 무시합니다.

A	5(=p)
B	8(=q)

각 배열에 원소가 하나씩 남았습니다(la=ra, lb=rb). 이때 마지막으로 2번의 질문을 사용하여 A의 la번째 원소와 B의 lb번째 원소를 질문합니다. 그리고 그 둘 중 더 크지 않은 값을 중앙값으로 선택하여 출력합니다. 위의 예시에서는 5가 그 중앙값이 되겠죠.

 

두 번째로 $p=q$일 때를 봅시다. A에서 p는 x/2번째 원소이고, B에서 q는 y/2번째 원소입니다. S에서 p와 q보다 앞쪽에 있는 원소는 x/2+y/2-2개이므로, q(=p)가 그 중앙값이 됩니다. 따라서 p를 출력하고 종료합니다.

 

코드

위의 풀이로 짠 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, p, q;
    cin >> n;
    if(n==1) {
        cout << "? A 1\n";
        cout << flush;
        cin >> p;
        cout << "? B 1\n";
        cout << flush;
        cin >> q;
        cout << "! " << min(p, q) << flush;
        return 0;
    }
    int la=1, lb=1, ra=n, rb=n;
    while(1) {
        if(la==ra && lb==rb) {
            cout << "? A " << la << "\n" << flush;
            cin >> p;
            cout << "? B " << lb << "\n" << flush;
            cin >> q;
            cout << "! " << min(p, q) << flush;
            break;
        }
        cout << "? A " << (la+ra)/2 << "\n" << flush;
        cin >> p;
        cout << "? B " << (lb+rb)/2 << "\n" << flush;
        cin >> q;
        if(p>q) {
            ra=(la+ra)/2;
            lb=(lb+rb)/2+1;
        }
        else if(p==q) {
            cout << "! " << p << flush;
            break;
        }
        else {
            la=(la+ra)/2+1;
            rb=(lb+rb)/2;
        }
    }
}

 

감사합니다.