[백준/BOJ] 25305번 커트라인 (C/C++)

백준 온라인 저지(BOJ) 25305번 커트라인
https://www.acmicpc.net/problem/25305

25305번: 커트라인

* 사용언어 : C언어, C++
 

1. 문제

N 명의 시험 점수가 주어졌을 때
그 중 K 명이 상을 받는 경우 가장 낮은 사람의 점수(커트라인)를 출력
 

2. 풀이

N 개의 점수를 배열에 입력받고
정렬한 뒤 k 번째, 즉 index 로는 k - 1 자리에 있는 점수를 출력하면 됩니다.
 
크기가 1,000인 작은 사이즈의 문제라서
어떤 정렬을 사용해서 구현해도 충분히 통과할 수 있을 것 같습니다.
 
저는 시간복잡도가 nlogn 인 merge sort 로 구현해서 풀었습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
25305_커트라인
1124KB	0ms
*/
#include <cstdio>

const int LM = 1000;
int a[LM], t[LM];

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (a[i] >= a[j]) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (k = s; k <= e; ++k) a[k] = t[k];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

	mSort(0, n - 1);

	printf("%d\n", a[k - 1]);
	return 0;
}