[백준] 1300번 - K번째 수 (C언어) [Gold2]

input	output
3 7	6

해당 문제는 단순히 이중 배열을 선언하여 정렬하려고 한다면 시간 초과가 발생할 것이다. 따라서  빠르게 해결할 수 있는 알고리즘인 이진 탐색(이분 탐색)을 사용하였다. 

 

기본적인 알고리즘은 아래와 같다.

low=1, high=n*n으로 설정

low <= high 일 동안 while문 루프
mid값 구하기
mid값보다 작거나 같은 수들 구하기 => cnt

cnt값이 목표 인덱스 보다 크거나 같을 경우
mid를 왼쪽으로 옮기기

cnt값이 목표 인덱스 보다 작을 경우
mid를 오른쪽으로 옮기기

루프 탈출 후 low값 출력

 

[n = 3 , k = 5 인 경우]

array[3][3]	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

*mid 값보다 작은 값들의 갯수를 구하는 함수 먼저 구현

ll func(ll x) { // mid보다 작은 수들의 개수를 시간 초과 없이 시간 복잡도 O(n) 으로 구현
	ll sum = 0;

	for (int i = 1; i <= n; i++){ 
		sum += min(x / i, n);
	}
	return sum;
}

mid = 5 

함수 결과 : 2 + 2 + 1 = 5

k	1	2	3	4	5	6	7	8	9
array[k]	1	2	3	2	4	6	3	6	9

mid 값보다 작은 값들의 갯수 : 5개

 

알고리즘을 이용하여 코드를 작성하면 전체 소스 코드는 아래와 같다.

/*
	low=1, high=n*n으로 설정
		low <= high 일 동안 while문 루프
			mid값 구하기
		mid값보다 작거나 같은 수들 구하기 => cnt
		
		cnt값이 목표 인덱스(K) 보다 크거나 같을 경우
		mid를 좀 더 왼쪽으로 옮겨야 한다.
		high = mid - 1
	
		cnt값이 목표 인덱스(K) 보다 작을 경우
		mid를 좀 더 오른쪽으로 옮겨야 한다.
		low = mid + 1
	루프 탈출 후 low값 출력
*/
#include <stdio.h>
#define min(a,b) (a) < (b) ? (a) : (b)
#pragma warning(disable:4996)
#define INF 1000000000
typedef long long int ll;
ll n, k;
ll low, high, mid;
ll cnt;

ll func(ll x) { // mid보다 작은 수들의 개수를 시간 초과 없이 시간 복잡도 O(n) 으로 구현
	ll sum = 0;

	for (int i = 1; i <= n; i++){ 
		sum += min(x / i, n);
	}
	return sum;
}

int main() {
	scanf("%lld%lld", &n, &k);

	low = 1;
	high = n * n;

	k = min((long long)INF, k);

	while (low <= high) { // 이진 탐색
		mid = (low + high) / 2;

		cnt = func(mid); 

		if (cnt >= k) { // cnt값이 목표 인덱스 보다 크거나 같을 경우
			high = mid - 1; // high 값 업데이트
		}
		else { // cnt값이 목표 인덱스 보다 작을 경우 
			low = mid + 1; // low 값 업데이트
		}
	}
	
	printf("%d", low); // 루프 탈출 후 low 값 출력

	return 0;
}

이진 탐색의 개념과 시간 복잡도를 줄일 수 있는 방법을 안다면 쉽게 해결 가능한 문제였다.

 

[1300번]

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

1300번: K번째 수

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview