[백준] 16498번 : 작은 벌점 (C++)

16498번 : 작은 벌점

---

문제)

세 명이 한 팀이 되어 정수를 조합하는 게임이 있다. 이 게임에서 각 팀의 각 플레이어는 정수가 하나씩 적혀있는 숫자 카드를 한 장 이상 받는다. 각 플레이어는 가지고 있는 숫자 카드 중 한 장을 선택해 책상에 내려 놓는다. 이렇게 되면 책상에 총 3장의 카드가 놓이게 되며, 이 때 보이는 수의 최댓값과 최솟값의 차이가 벌점이 된다. 이를 식으로 표현하면 다음과 같다.

 

| max(a,b,c) – min(a,b,c) |

 

여기서 a, b, c는 각각 플레이어가 선택하여 내려놓은 카드의 숫자 값이다.

세 명의 플레이어에게 주어진 숫자 카드가 주어졌을 때, 만들 수 있는 가장 작은 벌점을 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 첫 번째 플레이어가 받은 숫자 카드의 개수 A, 두 번째 플레이어가 받은 숫자 카드의 개수 B, 세 번째 플레이어가 받은 숫자 카드의 개수 C가 주어진다. (1 ≤ A, B, C ≤ 1,000)

 

둘째 줄에 첫 번째 플레이어가 받은 숫자 카드에 적힌 수, 셋째 줄에 두 번째 플레이어가 받은 숫자 카드에 적힌 수, 넷째 줄에 세 번째 플레이어가 받은 숫자 카드에 적힌 수가 주어진다.

 

숫자 카드에 적힌 수는 절댓값이 100,000,000보다 작거나 같은 정수이다..

 

 

 

출력 :

세 플레이어가 만들 수 있는 가장 작은 벌점을 출력한다.

 

 

 

 

 

 

 

풀이)

 

// 16498. 작은 벌점
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
long long answer = LLONG_MAX;
 
void search(vector<long long> v1, vector<long long> v2, vector<long long> v3)
{
    // v1, v2를 이용해 최대 최소값의 모든 경우의 수를 찾는다.
    for (int i = 0; i < v1.size(); i++)
    {
        for (int j = 0; j < v2.size(); j++)
        {
            // v1, v2를 기준으로 최대 최소값을 만들었다면
            long long max_num = max(v1[i], v2[j]);
            long long min_num = min(v1[i], v2[j]);
 
            // 이분 탐색을 2번 진행해, v3에서 사잇값이 존재하는지 찾는다.
            int s = 0;
            int e = v3.size() - 1;
 
            long long max_idx = -1;
 
            while (s <= e)
            {
                int mid = (s + e) / 2;
 
                if (v3[mid] <= max_num)
                {
                    max_idx = mid;
                    s = mid + 1;
                }
                else e = mid - 1;
            }
 
            s = 0;
            e = v3.size() - 1;
 
            long long min_idx = -1;
            while (s <= e)
            {
                int mid = (s + e) / 2;
 
                if (v3[mid] >= min_num)
                {
                    min_idx = mid;
                    e = mid - 1;
                }
                else s = mid + 1;
            }
 
            // 사잇값이 존재한다면 답을 갱신한다.
            if (max_idx != -1 && min_idx != -1 && max_idx - min_idx + 1 > 0)
            {
                answer = min(answer, abs(max_num - min_num));
            }
        }
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int a, b, c;
    cin >> a >> b >> c;
 
    vector<long long> player1(a);
    for (long long& ele : player1)  cin >> ele;
    sort(player1.begin(), player1.end());
    
    vector<long long> player2(b);
    for (long long& ele : player2)  cin >> ele;
    sort(player2.begin(), player2.end());
 
    vector<long long> player3(c);
    for (long long& ele : player3)  cin >> ele;
    sort(player3.begin(), player3.end());
 
    // 모든 경우의 수를 찾는다.
    search(player1, player2, player3);
    search(player1, player3, player2);
    search(player2, player3, player1);
    
    cout << answer;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/16498 

16498번: 작은 벌점