SWEA - 공평한 분배2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AY6cg0MKeVkDFAXt&categoryId=AY6cg0MKeVkDFAXt&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

가장 먼저 정렬하고 싶단 생각이 드는 문제이다. 

그리고 모든 경우의 수를 구해야하는데 조합으로 구하면 N이 50이기 때문에 불가능하다.

 

본인은 처음에 이분탐색을 생각했다. 

 

정렬을 한 후 lo, hi에서 lo, lo + 1  | hi, hi - 1 간의 차이가 더 큰 쪽으로 범위를 줄이도록 하였으나, 이 방법은 만약 차이가 같을 경우 문제가 발생하여 결국 테스트케이스를 20개정도 통과하지 못했다.

 

문제를 잘 보면 결국 정렬해준대로 어느 범위를 정해주면 그 숫자들은 모두 가져가야한다. 무슨 의미냐면

 

1 2 4 18 29 32 라고 할 때 K = 3이라면

 

1 4 18

1 2 18

 

이 두개는 분명 다른 조합이지만 답은 같아진다. 최솟값과 최댓값이 같기 때문이다. 그리고 이 것은 답이될 수 없다. 1보다 큰 수가 존재하기 때문이다. 그러므로 정렬한 후엔 K개 씩 넘어가면서 그저 최댓값 - 최솟값만 비교하면 답을 구할 수 있다. 

알고리즘보다 논리적으로 생각하는 문제였다. SWEA는 이런 문제가 많은 것 같다.

 

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

int main(){
    int T; cin >> T;

    for(int i = 0; i < T; i++){
        int N, K;
        int pocket[51];
        
        cin >> N >> K;

        for(int j = 0; j < N; j++){
            cin >> pocket[j];
        }

        sort(pocket, pocket + N);
        int answer = pocket[K - 1] - pocket[0];

        for(int k = 0; k < N - K + 1; k++){
                answer = min(answer, pocket[k + K - 1] - pocket[k]);
        }

        cout << '#' << i + 1 << " " << answer << '\n';
    }
}