https://www.acmicpc.net/problem/7795
문제
> 심해에는 두 종류의 생명체 A와 B가 존재한다.
> A는 B를 먹는다.
> A는 자기보다 크기가 작은 먹이만 먹을 수 있다.
> 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다.
8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.
> 두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.
접근
이분탐색을 사용할건데 이분탐색엔 lower_bound라는 함수를 사용해주면 된다.
찾으려는 값 이상의 값이 처음 나오는 인덱스를 반환해주기 때문에 이를 역으로 이용하면 그 인덱스 보다 작은 값들을 세면 된다는 것이다.
만약 그 값이 없으면 마지막 인덱스를 반환하기때문에 이를 포인터로 마지막 값이 찾으려는 값과 같은지만 검증하면 된다.
문제해결
> 테스트 케이스를 입력받고 그만큼 while문을 돌린다.
> A생명체, B생명체의 수를 입력받고, 벡터에 각 생명체의 크기를 입력받는다.
> 탐색을 써서 잡아먹을 대상을 찾을 B를 오름차순 정렬해준다.
> A의 각 생명체가 먹을 수 있는 B의 수를 구해야하므로 A의 수만큼 반복하며 lower_bound 함수를 사용한다.
> lower_bound 함수를 쓰면 B벡터에서 세번째 매개변수로 들어온 A[i]즉, A의 값이상인 값을 찾는다.
> it으로 특정 인덱스가 반환되면 예를 들어 1이 반환되면 B의 1번 인덱스 부터 그 뒤는 전부 A[i]와 같거나 큰 생명체이므로 문제에 맞지않는다.
> 따라서 나온 it값 보다 작은 인덱스에 있는 값들이 먹을 수 있는 생명체의 수가 된다.
그럼 1이 나왔으면 1보다 작은 인덱스는 0 이므로 1마리 먹을 수 있고, 3이면 0,1,2번 인덱스르 먹을 수 있으므로 it으로 나온 인덱스가 곧 먹을 수 있는 생명체의 수이다.
> 그래서 cnt에 it이 인덱스이므로 이를 정수로 바꿔주기 위해 b.begin()인 0을 빼서 정수형으로 바꿔주고 누적한다.
> 만약 A의 생명체가 B의 모든 생명체 보다 크다면 B내부에 찾으려는 값이 없어서 it에 b.end()값이 온다. 이는 B.size()값과 같다. 즉 B가 3,6,1 이고 A[i]가 8이면 없으므로 it에 b.end()인 3이 온다. 근데 결국 이 값은 B의 생명체 3마리 다 먹을 수 있다는 뜻이므로 예외처리없이 이 값도 cnt에 누적한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T, N, M;
cin >> T;
while (T--)
{
cin >> N >> M;
vector<int> A(N);
vector<int> B(M);
for (int i = 0; i < N; i++) cin >> A[i];
for (int i = 0; i < M; i++) cin >> B[i];
sort(B.begin(), B.end());
int cnt = 0;
for (int i = 0; i < A.size(); i++)
{
auto it = lower_bound(B.begin(), B.end(), A[i]);
cnt += (it - B.begin());
}
cout << cnt << '\n';
}
}
후기
mid, left, right값을 구해 범위를 감소해나가는 이분탐색 말고 lower, upper bound를 사용해 특정 값을 중간값처럼 써서 바로 연산하는 이분탐색을 해봤다. 확실히 편하고 간단하지만 it의 반환값이 iterator라 이를 값으로 쓰기위해 형변환과, it으로 값에 접근하기위해 포인터사용 등 신경써줘야 할 부분이 있기 때문에 놓치지 말자.
