[백준/C++] 1300번 - K번째 수

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

1300번: K번째 수

풀이

https://cocoon1787.tistory.com/292

[C/C++] 백준 1300번 - K번째 수 (이분 탐색)

이 문제는 예전에 한 번 풀고 다시 풀어본 문제이다. 예전에도 어려워서 다른 사람 코드를 보고 힌트를 얻어서 풀었는데 이번에도 역시 풀지 못하고 내 코드를 봐도 이해가 안 가서 위에 블로그를 참고해서 다시 풀었다.

 

이 문제의 핵심은 이분 탐색이고, 어떻게 이분 탐색을 활용하느냐가 핵심이다. 처음에 너무 어려워서 무식하게 수를 다 넣고 정렬해볼 생각밖에 하지 못하였다. 하지만 당연히 메모리 초과가 났고, 다시 이분 탐색으로 풀기 시작했다.

 

간단하게 이분 탐색을 설명해 보자면,

1. 일단 이분 탐색을 위해서는 무조건 정렬된 값이어야 한다.
2. 그중 가장 작은 값은 left, 가장 큰 값은 right로 설정한다.
3. middle값은 left와 right 사이의 중앙값으로 이 값으로 찾고자 하는 수와 비교한다.
   1. middle값을 left와 right 사이의 중앙값으로 초기화한다.
   2. 찾고자 하는 수를 k라 하면 k와 middle값을 비교한다.
   3. 만약 middle값이 k보다 작으면 left값을 middle +1, k보다 크면 right값을 middle - 1로 바꿔준다.
   4. middle과 k가 같거나 left가 right보다 커질 때까지 1 - 3번을 반복한다.

 

이 원리를 활용하여 K번째 수를 찾았다.

int lt = 1, rt = k, mid, cnt;

일단 이분 탐색을 위한 변수 선언을 하였다. lt는 left값으로 1부터 시작이므로 1로 초기화해주었고, rt는 right값으로 올 수 있는 가장 큰 값이므로 k를 넣어주었다. 문제에 B배열에서 가장 큰 값은 n*n값이지만 k번째의 수는 K보다 클 수 없기 때문에 rt값을 k로 초기화해주었다. 그리고 이분 탐색을 위한 mid와 개수를 세주기 위한 cnt변수를 선언해주었다. 또 k는 min(10^9, N2) 보다 작거나 같은 자연수이기 때문에 전부 int로 선언해주었다.

 

while (lt <= rt) {
    mid = (lt + rt) / 2;
    cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += min(n, mid / i);
    }
    if (cnt >= k) rt = mid - 1;
    else lt = mid + 1;
}

그다음 이분 탐색을 구현해주었다. whlile문을 돌려주었고, lt가 rt를 넘어서면 의미가 없어지기 때문에 조건은 lt가 rt보다 작거나 같을 때로 넣어주었다. mid값은 lt, rt의 중앙값으로 설정한 후 cnt를 0으로 초기화해주었다. cnt를 구해주는 이유는 k인 수를 찾는 게 아닌 k번째 수를 찾아야 하므로 mid보다 작거나 같은 수가 몇 개인지를 알아야 한다. 그 코드가 바로 for문이다.

 

for (int i = 1; i <= n; i++) {
    cnt += min(n, mid / i);
}

for문을 설명해 보자면 i행부터 n행까지 mid보다 작거나 같은 수를 다 count 하여 cnt에 저장하는 코드이다. min(n, mid / i)는 설명하자면 i행은 i의 배수가 있는 행이기 때문에 mid보다 작거나 같은 i의 배수의 개수는 mid / i이다. 또 n은 이 행렬은 n*n행렬이기 때문에 한 행에서 mid보다 작거나 같은 수의 최대 개수는 n 개다. 따라서 mid / i가 n보다 크다면 n을 더해주어야 한다.

 

if (cnt >= k) rt = mid - 1;
else lt = mid + 1;

그러고 나서 cnt와 k를 비교해 준다. cnt가 k보다 크거나 같다면 찾고자 하는 k번째 수는 mid와 같거나 mid보다 작은 수이다. 그럼 지금보다 더 작은 수로 비교를 해 줘야 하기 때문에 rt를 mid - 1로 바꿔주어야 한다. 만약 cnt가 k보다 작다면 찾고자 하는 수는 무조건 mid보다는 크다는 뜻이기 때문에 lt를 mid + 1로 바꿔주어야 한다.

 

계속해서 비교를 하며 lt와 rt값을 바꿔주다 보면 lt가 rt값보다 큰 경우가 발생하게 되고 그럼 while문의 조건에 따라 while문이 종료된다. 그러고 나서 lt값을 출력해주면 그 값이 답이 된다.

 

코드는 굉장히 짧지만 이분 탐색을 생각해 내는 것과 어떻게 이분 탐색을 활용할지를 생각해 내는 것이 굉장히 어려웠다. 앞으로 이분 탐색 문제를 좀 더 많이 풀어봐야겠다.

 

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;

	int lt = 1, rt = k, mid, cnt;

	while (lt <= rt) {
		mid = (lt + rt) / 2;
		cnt = 0;

		for (int i = 1; i <= n; i++) {
			cnt += min(n, mid / i);
		}

		if (cnt >= k) rt = mid - 1;
		else lt = mid + 1;
	}

	cout << lt;
	return 0;
}