먹느냐 먹히느냐

이번 글에서는 입력받은 A와 B의 크기를 비교하여 A가 B를 먹을 수 있는 쌍의 개수를 세는 문제를 해결하는 방법에 대해 알아보겠슴민다.

우선, 문제에서 요구하는 대로 A와 B의 크기를 입력받아 배열 g와 h에 저장합니다. 그리고 g 배열의 모든 원소와 h 배열의 모든 원소를 비교하여 g 배열의 원소가 h 배열의 원소보다 크면 쌍의 개수를 1씩 증가시키는 방식으로 문제를 해결할 수 있습니다.

---

문제설명

깊은 바다 아래에는 A와 B라는 두 종류의 생물이 있습니다.

A는 B의 포식자이지만, A는 크기가 B보다 큰 경우에만 B를 먹습니다.

예를 들어, A종의 크기 = {8, 1, 7, 3, 1}이고, B종의 크기 = {3, 6, 1}이면, A가 B를 먹는 쌍은 7쌍이 있습니다.

( A>B: 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1 )

A종과 B종의 각 유기체의 크기가 주어졌을 때, A가 B를 먹을 수 있는 쌍이 몇개인지 세는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트케이스의 개수 T가 입력된다.

각 케이스의 첫째 줄에는 A와 B의 크기인 N, M이 입력된다.

N(1 ≤ N ≤ 20,000),  M(1 ≤ M ≤ 20,000)

둘째 줄에는 A의 데이터가 공백으로 분리되어 N개 입력된다.

셋째 줄에는 B의 데이터가 공백으로 분리되어 M개 입력된다.

출력

A가 B보다 큰 AB쌍의 수를 각각 출력한다.

예시

입력

2 5 3 8 1 7 3 1 3 6 1 3 4 2 13 7 103 11 290 215

출력

7 1

---

순서도

1. 변수 a, s, d, k 선언
2. 배열 g[20001], h[20001] 선언
3. k = 0;
4. a입력
5. a번 반복
   5.1. 정수 변수 s와 d를 사용자로부터 입력 받음
   5.2. s만큼 입력
   5.3. d만큼 입력
   5.4. if (g[j] > h[i])  k++
   5.5. k 출력
   5.6. k = 0;
6. 종료

 

---

코드설명

#include <stdio.h>
main()
{
   int a, s, d, g[20001]={}, h[20001]={}, k=0;
   scanf("%d", &a);
   for(int i=0; i<a; i++)
   {
      scanf("%d %d", &s, &d);
      for(int j=0; j<s; j++)
      scanf("%d", &g[j]);
      for(int j=0; j<d; j++)
      scanf("%d", &h[j]);
      for(int j=0; j<s; j++)
      {
         for(int l=0; l<d; l++)
         if(g[j]>h[l])
         k++;
      }
      printf("%d\n", k);
      k=0;
   }
}

 

오류해결과정 : 3중 for문을 쓰지 않기 위해 재귀함수를 사용했는데 코드가 꼬여버려서 얌전히 3중 for문을 사용했습니다..

 

---

위 코드를 실행하면 입력받은 A와 B의 크기를 비교하여 A가 B를 먹을 수 있는 쌍의 개수를 출력해줍니다.

실행화면