[C++] 백준 7795번 먹을 것인가 먹힐 것인가

1. 문제이해

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

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

 

두 종류의 생명체 A, B가 있고, A는 B를 먹는다.

단, A는 자기보다 작은 B만 먹을 수 있다.

테스트 케이스의 개수(T)와, 각 테스트케이스에서의 A, B의 수와 크기가 주어질 때,

A가 B를 먹을 수 있는 순서쌍의 개수를 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

A와 B의 수, 각각의 크기들이 주어질 때, A가 B를 먹을 수 있는 경우,

즉, A의 크기가 B의 크기보다 큰 순서쌍의 개수를 구하는 것이 목표이다.

 

문제는 간단하다.

A의 크기가 B의 크기보다 큰 경우들을 하나하나 확인해나가며,

그때마다 count하는 변수값을 증가시켜주기만 하면 된다.

 

주의해야 할 점은 시간초과인데,

이는 cin, cout 을 scanf, printf 로 바꾸어주었더니 바로 해결되었다.

(cin, cout보다 scanf, printf의 동작이 더 빠른 듯하다.

cin.tie(0); ios::sync_with_stdio(0); 를 사용했음에도 전자는 시간초과가 발생했다.)

 

 

 

3. 소스코드

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

int main() {
	int T;
	int N, M;
	int setA[20000];
	int setB[20000];

	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		int count = 0;
		scanf("%d %d", &N, &M);

		for (int j = 0; j < N; j++) {
			scanf("%d", &setA[j]);
		}

		for (int j = 0; j < M; j++) {
			scanf("%d", &setB[j]);
		}

		// 입력받은 A와 B의 크기 정렬
		sort(setA, setA + N);
		sort(setB, setB + M);

		// A가 B를 잡아먹을 수 있는지 확인
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				// A의 크기가 더 크면, 잡아먹을 수 있으므로 count
				if (setA[j] > setB[k]) {
					count++;
				}

				else {
					break;
				}
			}
		}

		printf("%d\n", count);

	}

	return 0;
}

각 테스트 케이스의 경우의 수(T)와, 각 경우의 A의 개수(N)과 B의 개수(M),

A의 크기들(setA)과 B의 크기들(setB)을 입력받고 작업을 수행했다.

 

입력값을 모두 입력받은 후에는, A, B의 크기를 모두 정렬해주었다.

이후, 아래 for문을 통해 A가 B를 잡아먹을 수 있는지,

즉, A의 크기가 B의 크기보다 큰지 확인했다.( if (setA[j] > setB[k]) )

만약, A가 B를 잡아먹을 수 있다면, count값을 증가시켜주고,

완전탐색이 끝난 후 count값을 출력해주었다.

 

 

---

필자는 완전탐색을 이용해 풀었지만,

이진탐색을 이용해보아도 좋을 것 같다.

다음에는 이진탐색으로 풀어서 풀이를 올려볼까..🤔