[G5] 백준 16498번 작은 벌점 C++ 정렬, 3포인터

리뷰

 

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

쉽게 접근했다가 WA를 연달아 맞고, 3포인터를 통해 최적해를 뽑아내는 로직으로 변경하였다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• a, b, c : 각 플레이어의 숫자 카드 개수를 저장할 변수
• as, bs, cs : 각 플레이어의 숫자 카드 정보를 저장할 배열

 

함수

없음

 

 

문제풀이

1. a, b, c값을 입력 받고, 각 플레이어의 숫자 카드 정보를 입력 받아 as, bs, cs배열을 초기화한다.
2. sort함수를 통해 as, bs, cs배열을 오름차순으로 정렬한다.
3. 변수 i, j, k를 0으로 초기화 하고, ans를 매우 큰 값으로 초기화한다.
4. i가 a보다 작고, j가 b보다 작으며, k가 c보다 작은 경우를 조건으로 하는 while루프를 개행한다.
5. 변수 mn에 as[i], bs[j], cs[k]의 최소값을 저장한다.
6. 변수 mx에 as[i], bs[j], cs[k]의 최대값을 저장한다.
7. ans와 mx-mn을 비교하여 더 작은 값을 ans에 저장한다.
8. 최소값이 as[i]였다면 i를 증가, bs[j]였다면 j를 증가, 아니라면 k를 증가시킨다.
9. while루프가 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. 초기 배열을 정렬 처리하지 않아 제출 시 WA를 받았다.
2. 브루트포스 + lower_bound기반의 이진 탐색을 수행 후 제출하였으나 WA를 받았다. 반례는 찾지 못했다.
3. 3포인터 방식으로 리팩토링하여 제출 시 AC를 받았다.

 

참고 사항

1. 숫자 카드에 적힌 수는 절댓값이 100,000,000보다 작거나 같은 정수이다.
2. 결국 최대값과 최소값의 차가 가장 작은 경우를 찾아야 한다.

 

정답 코드

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

const int N = 1e3;
int a, b, c;
int as[N], bs[N], cs[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b >> c;
    for (int i = 0; i < a; ++i) cin >> as[i];
    for (int i = 0; i < b; ++i) cin >> bs[i];
    for (int i = 0; i < c; ++i) cin >> cs[i];

    sort(as, as + a);
    sort(bs, bs + b);
    sort(cs, cs + c);

    int i = 0, j = 0, k = 0;
    int ans = 2e9;

    while (i < a && j < b && k < c) {
        int mn = min({ as[i], bs[j], cs[k] });
        int mx = max({ as[i], bs[j], cs[k] });

        ans = min(ans, mx - mn);

        if (mn == as[i]) ++i;
        else if (mn == bs[j]) ++j;
        else ++k;
    }

    cout << ans;
}