728x90
문제 7795번
https://www.acmicpc.net/problem/7795
이 문제는 이진탐색으로 풀었다. 일단 테스트 케이스가 몇개인지 입력받아 반복문으로 묶어준다.
vector A,B를 N,M크기만큼 만들어(배열처럼 입력받으려고) 입력받아주고, 해당 벡터들을 정렬(이진탐색을 하기위한 필수조건)한다. A의 크기인 N만큼 반복하여 N이 먹을 수 있는 숫자가 있는지 탐색한다. 여기서 while문의 조건은 start+1<end로 해주어 값이 있는 부분만 확인할 수 있게 했다. 저렇게 하면 start와 end의 바로 앞에 있을 때 반복문을 빠져나온다. 그리고 A와 B를 각각 비교하여 A가 더 크면 start를 mid로 옮겨주고, A가 더 작거나 같으면 end를 mid로 옮긴다. 그렇게 하다가 반복문을 빠져나왔을 때 해당 start값을 count에 넣어준다. 그런데 start값은 인덱스 값이기 때문에 원래 개수보다 1이 더 작다. 그러므로 만약 인덱스에 start를 넣은 B값이 A보다 작으면 하나를 더 증가시킨다. 여기서 조건문을 달아준 이유는 먹을 수 있는 개수가 없어 start가 0이 된 경우가 있기 때문이다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int T, N, M;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N >> M;
vector <int> A(N), B(M);
for (int j = 0; j < N; j++) {
cin >> A[j];
}
for (int k = 0; k < M; k++) {
cin >> B[k];
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int count = 0;
for (int j = 0; j < N; j++) {
int start = 0, end = M;
while (start+1 < end) {
int mid = (start + end) / 2;
if (A[j] > B[mid]) {
start = mid;
}
else {
end = mid;
}
}
count += start;
if (A[j] > B[start]) {
count++; //인덱스가 0부터니까 1 더하기
}
}
cout << count << '\n';
}
return 0;
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 2110번 - 공유기 설치 (0) | 2024.04.18 |
---|---|
[C++] 백준 1654번 - 랜선 자르기 (0) | 2024.04.17 |
[C++] 백준 1225번 - 이상한 곱셈 (0) | 2024.04.15 |
[C++] 백준 1264번 - 모음의 개수 (0) | 2024.04.14 |
[C++] 백준 7567번 - 그릇 (0) | 2024.04.12 |