[백준 7795] 먹을 것인가 먹힐 것인가

7795번: 먹을 것인가 먹힐 것인가 (acmicpc.net)

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

 

배운 것

이분탐색 이용 

upper_bound

• 용도 : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
• ⭐ 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	vector<int> arr = { 1,2,3,4,5,6 };
	cout << "upper_bound(3) : " << upper_bound(arr.begin(), arr.end(), 3) - arr.begin();

    // 결과 -> upper_bound(3) : 3
	return 0;
}

 

lower_bound

• 용도 : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
• ⭐ 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5

	return 0;
}

---

 

정답 코드 - upper_bound

#include <bits/stdc++.h>
using namespace std;
int a[20001];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int T;cin>>T;
  while(T--){
    int n,m;cin>>n>>m;
    for(int i=0;i<n;++i) cin>>a[i];
    sort(a, a+n);
    int ans = 0;
    for(int i=0;i<m;++i){
      int num;cin>>num;
      int index = upper_bound(a, a+n, num) - a;
      ans += n - index;
    }
    cout<<ans<<'\n';
  }
}
/*
이분탐색을 이용한 풀이
*/

 

 

 

참고

알고리즘 - c++ lower_bound, upper_bound 활용하기 | ChanBLOG (chanhuiseok.github.io)