[C++] 먹을 것인가 먹힐 것인가 (7795번)

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

7795번: 먹을 것인가 먹힐 것인가

---

문제풀이

n과 m의 크기가 최대 20000이므로, 완전탐색을 하면 시간초과가 발생할 것이라고 생각했다. 더 좋은 방법을 생각하던중, 두 값을 정렬한 뒤 a를 순회하며 b에 이분탐색을 한 뒤 인덱스를 이용해서 더 작은 값의 개수를 구할 수 있다고 생각했다.

풀이 방법이 바로 떠올라서 풀었는데, 이분탐색에서 막혀버렸다. 맨날 공식처럼 그냥 "값이 있는 경우"일 때만 이분탐색을 써서 찾다보니, lower bound 즉 찾은 인덱스의 값이 찾을 값보다 작거나 같아야 하는 경우에 대한 이분탐색 방법이 쉽게 떠오르지 않아 다른 사람의 해설을 참고했다.

 

lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치를 말한다. 데이터가 들어있는 배열을 A[n], 찾고자 하는 값을 k, 중간 값을 m, 구간을 l, h 라고 할 때, A[m-1] < k 이면서 A[m] >= k 를만족하는 최소 m을 찾는 것을 말한다.

 

일반적인 이분탐색과 다르게 h의 값이 n-1이 아니라 n이어야 한다. k가 배열의 모든 원소보다 클 경우를 처리해 주기 위함이다.

예를들어 7을 찾을거고 배열이 1, 3, 6일 경우, h를 n-1로 하면 m이 2가 되고, n으로 하면 3이된다.

 

또한 A[m] >= k를 만족해야 하므로, A[m] < k 일 경우에는 low = middle + 1 이어야 하고, A[m] >= k 일 경우에는 high = middle 이어야 한다.

stl 라이브러리에 이 lower_bound를 구하는 함수가 존재한다. algirithm을 include해서 사용할 수 있다. 마찬가지로  upper_bound 함수도 존재한다.

std::lower_bound(A, A+n, k, [compare])

 

 

생각보다 어렵다. 공부해서 반드시 이해하고 넘어가자.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        long long a[20000], b[20000];
        for(int i=0; i<n; i++) cin >> a[i];
        for(int i=0; i<m; i++) cin >> b[i];
        long long answer = 0;

        sort(a, a+n);
        sort(b, b+m);

        for(int i=0; i<n; i++) {
            int high = m;
            int low = 0;
            int middle;
            while(low < high){
                middle = (high+low)/2;
                // cout << low << " " << high << " " << middle << endl;
                if(a[i] > b[middle]) {
                    low = middle+1;
                }
                else {
                    high = middle;
                }
            }
            answer += middle;
            // a[i] > b[middle]이면 현재 인덱스도 조건에 부합하므로 1 증가 시켜준다.
            if(middle < m && a[i] > b[middle]) answer++;
            // cout << middle << endl;
        }
        cout << answer << "\n";
    }
    return 0;
}

 

참고

https://12bme.tistory.com/120