백준 c++ 7795 문제 풀이

문제 링크 : https://www.acmicpc.net/problem/7795

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 3 문제 입니다.

문제명 : 먹을 것인가 먹힐 것인가

 

내 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;

    while (n--)
    {
        int a, b;
        cin >> a >> b;
        vector<int> av(a), bv(b);

        for (int i = 0; i < a; ++i)
        {
            cin >> av[i];
        }
        for (int i = 0; i < b; ++i)
        {
            cin >> bv[i];
        }

        sort(bv.begin(), bv.end());

        int result = 0;

        for (int i = 0; i < a; ++i)
        {
            result += upper_bound(bv.begin(), bv.end(), av[i] - 1) - bv.begin();
        }

        cout << result << '\n';
    }



}

 

문제 풀이 해석 내용

 

테스트 케이스 개수 입력

int n; // 테스트 케이스 개수
cin >> n;

int n;: 처리할 테스트 케이스의 총 개수를 저장하는 변수입니다.
cin >> n;: 사용자로부터 테스트 케이스의 개수 n을 입력받습니다.

 

 

테스트 케이스 처리 루프

while (n--) // n번 반복 (각 테스트 케이스 처리)
{
    // ... (내부 코드) ...
}

while (n--): n번 반복하는 루프입니다. 루프가 한 번 실행될 때마다 n의 값이 1씩 줄어들어 0이 되면 루프가 종료됩니다. 각 반복은 하나의 테스트 케이스를 처리합니다.

 

 

각 테스트 케이스 내부 - 배열 크기 및 요소 입력

    int a, b; // 첫 번째 배열 크기 a, 두 번째 배열 크기 b
    cin >> a >> b;
    vector<int> av(a), bv(b); // a 크기의 벡터 av, b 크기의 벡터 bv

    for (int i = 0; i < a; ++i)
    {
        cin >> av[i]; // 첫 번째 배열 요소 입력받아 av에 저장
    }
    for (int i = 0; i < b; ++i)
    {
        cin >> bv[i]; // 두 번째 배열 요소 입력받아 bv에 저장
    }

int a, b;: 첫 번째 배열 av의 크기 a와 두 번째 배열 bv의 크기 b를 저장하는 변수입니다.
cin >> a >> b;: 사용자로부터 a와 b 값을 입력받습니다.
vector<int> av(a), bv(b);: 크기가 a인 정수형 벡터 av와 크기가 b인 정수형 벡터 bv를 만듭니다.
두 개의 for 루프를 사용하여 각각 a개와 b개의 정수를 입력받아 av와 bv 벡터에 순서대로 저장합니다.

 

 

두 번째 배열 정렬

sort(bv.begin(), bv.end());

sort(bv.begin(), bv.end());: 벡터 bv에 저장된 모든 정수를 오름차순 정렬합니다. 

이 단계는 upper_bound 함수를 사용하기 위해 필수적입니다. upper_bound는 정렬된 범위에서만 올바르게 작동합니다.

 

 

결과 계산 및 누적 및 결과 출력

int result = 0; // 결과 (av[i] 보다 작은 bv 요소의 총 개수) 초기화

for (int i = 0; i < a; ++i) // 첫 번째 배열 av의 각 요소에 대해 반복
{
    // bv에서 av[i] - 1 보다 큰 첫 번째 요소의 위치 찾기
    // -> 이는 bv에서 av[i] 보다 작은 요소의 개수와 같습니다.
    result += upper_bound(bv.begin(), bv.end(), av[i] - 1) - bv.begin();
}

cout << result << '\n'; // 최종 결과 출력 후 줄바꿈

int result = 0;: 최종 결과를 저장할 변수입니다. 이 변수에는 av의 각 요소보다 작은 bv 요소의 총 개수가 누적됩니다.
for 루프를 사용하여 첫 번째 배열 av의 각 요소에 대해 반복합니다.

upper_bound(bv.begin(), bv.end(), av[i] - 1): std::upper_bound 함수를 사용합니다.
bv.begin(), bv.end(): 정렬된 벡터 bv 전체 범위를 나타냅니다.

av[i] - 1: upper_bound가 찾을 기준 값입니다. upper_bound(range, value)는 range 내에서 value보다 큰 첫 번째 요소의 위치(이터레이터)를 반환합니다. 따라서 upper_bound(bv.begin(), bv.end(), av[i] - 1)는 bv에서 av[i] - 1보다 큰 첫 번째 요소의 위치를 찾습니다. 이는 다시 말해 bv에서 av[i]보다 작거나 같은 마지막 요소 다음 위치를 찾는 것과 같습니다.

... - bv.begin(): upper_bound가 반환한 이터레이터에서 bv.begin() 이터레이터를 빼면, 해당 위치까지의 요소의 개수(즉, bv에서 av[i] - 1 이하의 요소 개수)를 얻게 됩니다. 이 개수는 결국 bv에서 av[i]보다 작은 요소의 개수와 동일합니다.
result += ...: 계산된 개수를 result에 더하여 누적합니다.

 

현재 테스트 케이스에 대한 최종 결과(result, 즉 av의 각 요소보다 작은 bv 요소의 총 개수)를 출력하고 줄바꿈합니다.

 

 

실행 결과