728x90
가장 먼저 정렬하고 싶단 생각이 드는 문제이다.
그리고 모든 경우의 수를 구해야하는데 조합으로 구하면 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';
}
}
'SWEA' 카테고리의 다른 글
SWEA - 백만 장자 프로젝트 (C++) (0) | 2024.05.18 |
---|---|
SWEA - 증가하는 사탕 수열 (C++) (0) | 2024.05.17 |
SWEA - 영어 공부(C++) (0) | 2024.02.02 |
SWEA - 10806번 수 만들기 (C++) (0) | 2024.01.19 |
SWEA - 햄버거 다이어트 (C++) (1) | 2023.12.15 |