[백준 문제 C++] 1300 K번째 수

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

1300번: K번째 수

#include <iostream>

using namespace std;

int GetMin(int a, int b)
{
	return a < b ? a : b;
}

int BinarySearch(int n, int k)
{
	int left = 1, right = k;

	while (left < right)
	{
		int mid = (left + right) / 2;
		int count = 0;

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

		if (count < k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}

	return right;
}

int main()
{
	int n, k;
	cin >> n >> k;

	cout << BinarySearch(n, k) << endl;
}

다른 분들이 짠 코드를 봤는데 결국 똑같은 코드가 되어버렸다.

처음에 문제를 봤을 때 이걸 어떻게 이진탐색으로 푸는거지?? 생각이 들었지만 지금은 이해가 되었다.

 

문제는 이렇다.

2차원 n x n 크기의 배열 A가 있다. (모든 인덱스는 1부터 시작)

각 인덱스에 따라 [i][j] = i x j 의 값이 들어있다.

예를 들어

n = 3이면

 

[1][1] 1x1 = 1  [1][2] 1x2 = 2  [1][3] 1x3 = 3

[2][1] 2x1 = 2  [2][2] 2x2 = 4  [2][3] 2x3 = 6

[3][1] 3x1 = 3  [3][2] 3x2 = 6  [3][3] 3x3 = 9

 

이 배열을 B라는 1차원 오름차순 배열로 만든다.

B[1] = 1

B[2] = 2

B[3] = 2

B[4] = 3

B[5] = 3

B[6] = 4

B[7] = 6

B[8] = 6

B[9] = 9

 

이 중에서 k번째의 값은 무엇인가?

   k가 7이라면 B[7] = 6

 

위의 코드에서 핵심은 count를 세는 방법에 있다.

다시 한번 배열을 살펴보면

 

[1][1] 1x1 = 1  [1][2] 1x2 = 2  [1][3] 1x3 = 3        i = 1의 배수

[2][1] 2x1 = 2  [2][2] 2x2 = 4  [2][3] 2x3 = 6        i = 2의 배수

[3][1] 3x1 = 3  [3][2] 3x2 = 6  [3][3] 3x3 = 9        i = 3의 배수

 

즉 각 배수로 나누어봐서 그 결과가 내가 찾는 인덱스 값과 같다면 해당 숫자가 정답이 된다.

만약에 내가 B[4] (3)를 찾고 싶다면 위의 코드는 이렇게 동작이 된다.

 

left = 1, right = 4

mid = (1 + 4) / 2 = 2

 

for

i = 1   count += 2 / 1 (2)

i = 2   count += 2 / 2 (1)

i = 3   count += 2 / 3 (0)

 

count = 3으로 "2" 는 3번째 숫자란 의미가 된다.

4번째 숫자를 찾고 싶기 때문에

left = mid + 1을 해주고 다시 탐색을 해본다.

 

left = 3, right = 4

mid = (3 + 4) / 2 = 3

 

for

i = 1  count += 3 / 1 (3)

i = 2  count += 3 / 2 (1)

i = 3  count += 3 / 3 (1)

 

count = 5가 된다. 그러나 걱정할거 없다. 이미

B[3] = 2

B[4] = 3

B[5] = 3

으로 사잇값은 3으로 동일하기 때문이다.

 

추가적으로 GetMin(mid / i, n) 을 통해 더 작은 값으로 판별해주는데 예를 들어

 

6 x 6 배열에서

36번째를 찾게 된다면

left = 1, right = 36

mid = (1 + 36) / 2 = 18

 

i는 1일 때 18 / 1 = 18이 되어버린다.

n = 6 이므로 1x6 까지밖에 없는데 말이다.

수의 개수가 n을 넘어가버리면 모두 가능한 수로 취급하면 된다. mid / i, n 둘 중 작은 수를 더해주면 된다.