백준 알고리즘 7795번 : 먹을 것인가 먹힐 것인가
링크
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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)
출력
각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.
예제 입력 및 출력
풀이 코드(C++)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 10001
#define MOD 1000000003
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
int tc; // 테스트 케이스
int main(){
fastio;
cin >> tc;
int a,b;
while(tc--){
cin >> a >> b;
int cnt = 0;
vector<int> A(a),B(b);
for(int i = 0; i < a; i++) cin >> A[i];
for(int j = 0; j < b; j++) cin >> B[j];
sort(A.begin(),A.end());
sort(B.begin(),B.end());
for(int i = 0; i < a; i++){
for(int j = 0; j < b; j++){
if(A[i] == B[j]) break;
else if(A[i] > B[j]) cnt++;
else continue;
}
}
cout << cnt << "\n";
}
return 0;
}
시간초과 때문에 애를 먹었던 문제...
Author And Source
이 문제에 관하여(백준 알고리즘 7795번 : 먹을 것인가 먹힐 것인가), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inwooleeme/백준-알고리즘-7795번-먹을-것인가-먹힐-것인가저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)