백준 - 1300 K번째 수 C++ 풀이

문제 링크: www.acmicpc.net/problem/1300

1300번: K번째 수

문제 설명

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A [i][j] = i×j이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N 이 된다. B를 오름차순 정렬했을 때, B [k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다.
k는 min(10^9, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

예제 입력                                                                 예제 출력

3 7

6

 문제풀이

처음에 이분 탐색으로 푸는 문제인지 모르고 다음과 같은 코드를 짰는데 시간 초과 나왔다.

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

vector<long long> v;
long long n,n2;

int main() {
	cin >> n>>n2;
	for (long long i = 1; i < n+1; i++) {
		for (long long j = 1; j < n+1; j++) {
			v.push_back(i*j);
		}
	}
	sort(v.begin(), v.end());
	cout << v[n2] << endl;
}

 

 어떻게 풀어야 하는지 찾아보는데 알고리즘 분류가 이분 탐색으로 되어 있어서 깜짝 놀랐다. 단순히 정렬을 이용해서 푸는 문제인 줄 알았는데 이분 탐색을 이용하라니.. 감이 안 잡혀서 질문검색을 하다가 아래 질문에 대한 답을 보고 감을 잡고 문제를 풀 수 있게 되었다.

www.acmicpc.net/board/view/37110

글 읽기 - 소스코드 및 해설을 봐도 잘 모르겠습니다.

이분 탐색을 이용하는 알고리즘을 설명하자면 다음과 같다.

먼저 몇 번째로 오는 수를 보는 관점을 바꿔야 한다. 우리가 원하는 숫자는 배열중에서 k번째로 작은 숫자가 아니라 배열 안에 해당 숫자 크기 이하의  숫자가 적어도 k 개가 있다고 생각하는 것이다. 예를 들어 다음과 같이 오름차순으로 정렬된 숫자 배열 2 4 6 8 9에서 3번째로 작은 숫자인 6은 6 이하인 수를 3개 가지고 있다고 생각할 수 있는 것이다. 이를 이용하기 위해 우리는 p(x)라는 함수를 정의할 것이다.

p(x)는 N*N크기의 행렬 안에 값들 중 x보다  같거나 작은 수가 몇 개 있는지 반환해주는 함수이다. 그래서 임의의 x를 집어넣었을 때 p(x)<k 라면 x라는 수는 k번째 수보다 작은 수라는 뜻이고 p(x) > k 라면 x라는 수는 k번째 수보다 크거나 k번째 수와 같을 수 있다.  왜 k 번째 수와 같을 수 도 있냐면  중복되는 숫자가 있기 때문이다. 예를 들어 다음과 같은 숫자 배열이 있다고 하자 [ 1, 2, 3, 3, 3, 3 , 4 ,5] 그리고 k=4라고 한다면 우리가 원하는 숫자는 3이 되지만 p(3)=6이 된다. 또 추가적으로 p(x) == k 일 때  무조건 x는 k번째 숫자라고 생각할 수 있는데 Row * Col로 만드는 숫자 배열에는 빈 공간이 있기 때문에 p(x) ==k라고 해서 무조건 x가 정답이 될 수는 없다. 예를 들어 다음과 같은 배열이 있다고 생각해보자
[ 1, 2, 4, 6, 7] 그리고 k=3이라면 우리가 원하는 수는 4가 될 것이고 p(4) == k == 3을 만족한다. 그런데 이때 x=3 보다 x=5가 먼저 계산된다고 생각해보면 p(5) ==3 이기 때문에 5가 답으로 나오는 상황이 발생할 수 있다. 그렇기 때문에 우리는 p(x)==k더라도 p(x)==k를 만족하는 수가 더 있는지 확인해봐야 한다.

 위와 같은 추론을 통해 내릴 수 있는 결론은 우리가 찾는 k번째 수는 p(x)>=k를 만족하는 가장 작은 x 값이라는 것이다. 이 x 값을 빠르게 찾기 위해서 우리는 이분 탐색을 사용할 것이다. 이제 코드를 통해서 설명하도록 하겠다.

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

long long n,k;

long long p(long long value) {
	long long sum = 0;
	for (long long i = 1; i < n + 1; i++) {
		sum += min(n, value / i);
	}
	return sum;
}
void binary_search() {
	long long first = 1;
	long long end = n * n;
	long long ret;
	while (first<=end) {
		long long mid = (first+end) / 2;
		if (p(mid) < k) {
			first=mid-1;
		}
		else {
			ret = mid;
			end = mid - 1;
		}
	}
	cout << ret << endl;
}



int main() {
	cin >> n >> k;
	binary_search();
}

먼저 p() 함수는 앞서 말했듯이 입력받은 수보다 작거나 같은 수가 몇 개 인지 계산해준다. 계산하는 법은 row 값으로 나눈 몫의 수만큼으로 하되 n보다 몫의 수가 많을 수도 있으므로 min(), 함수를 이용하여 정확하게 계산할 수 있게 하였다.

binary_search() 함수는 우리가 잘 아는 이분 탐색 알고리즘과 유사하게 만들었다. 시작은 최솟값 1 끝은 최댓값 n*n으로 두어 그 두 수의 중간점을 이용함으로써 좀 더 효율적으로 원하는 원소를 찾아내게 만들었다. while문을 이용하여 반복해서 탐색하게 하였는데  p(mid)>=k 일 때 mid 값이 k번째 수가 될 수 있으므로 ret를 이용하여 계속 값을 저장해주었다. 이 반복문에서 유일하게 break 할 수 있는 조건은 first <= end이다. 반복문이 끝나면 가장 최근에 저장된 ret값을 출력한다.