백준 1300 K번째 수

K번째 수 (백준 1300)

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

아 팀 프로젝트 시작하면서 코테를 풀 수 있는 기간이 줄어드는 느낌이다
현재는 ‘3D’ 관련 작업을 하다, ‘크롤링’ 관련 작업을 하고
잠시 ‘크롤링’하면서 시간이 남아 코테와 TIL을 작성한다

일단 이 문제도 처음 볼 때,
왜 이진 탐색인지를 몰랐다

어떻게든 규칙을 찾아 풀려고
연습장에 ‘정사각형’을 그린 후
1x1… nxn 기준으로 ‘대칭’이 되니까
각 행 사이의 값은 2 x (n - i)개가 되므로…
그걸 세어주면서 문제를 풀면 되겠다!
했지만 깊게 생각을 하기 힘든 환경이었고, 어찌어찌 코드를 제출했으나 바로 틀렸다

다른 블로그들을 참고하여 보다
왜 이진탐색이라는 말인지를 다시 깨달았다
(사실 문제 분류에 ‘이진탐색’이라 적혀있는데)

일단 문제의 요점인 ‘이진 탐색’도 중요하지만
몇가지 전제 조건으로 로직을 짜내는 것도 중요하다고 느꼈다

Code

#include<iostream>
#include<math.h>

using namespace std;

typedef unsigned long long ull;

ull getCnt(ull _Mid, ull _N)
{
	ull ret = 0;

	// 요점은 mid(중간값)보다 작은 수의 개수를 구하는 것이다
	// 각 행의 요소들의 값이 A(i,j) = i x j 라는 것이 문제에 써져있다
	// 따라서 각 행에서 나올 수 있는 mid 보다 작은 요소들의 개수는
	// 일단 최대 N개
	// 그리고 _Mid를 i(행)으로 나누면 각 요소들의 1,2,3...N 번쨰 요소들과 비교가 가능하다
	// ex Mid가 8이고 N이 5일 때,
	// i가 2이면, A(2,5) = 10 보다는 작으며 나머지 요소들보다는 크거나 같음
	// 따라서 4개가 됨
	// 같은 값의 요소들을 '일렬'로 세우면 같은 위치에 오지만
	// 반대로 각 행에서 특정한 값보다 작은 수를 합하여
	// '개수'를 뽑아낼 수 있음
	// 우리가 구하는 것은 특정한 개수 'K' 와 일치하는
	// 실제 '요소'의 값을 구하는 것
	// 그렇기에 mid를 이용하여 구할 수 있다

	for (ull i = 1; i <= _N; i++)
	{
		ret += min(_Mid / i, _N);
	}

	return ret;
}

int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	ull n, k;
	cin >> n >> k;

	ull low = 1, high = n * n;

	// low <= high일 때까지 루프
	// mid 값을 구한다
	// mid 보다 바로 작은 수 구하기 (이걸 cnt)
	// cnt가 k 보다 크거나 같다면 high = mid -1
	// cnt가 k보다 작다면 low = mid + 1
	// 이후 low 출력

	ull mid = 0, cnt = 0;
	while (low <= high)
	{
		mid = (low + high) / 2;
		cnt = getCnt(mid, n);

		if (cnt >= k)
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}

	cout << low;

	return 0;
}

해결 아이디어

1. 문제의 전제조건을 읽어보면 우리가 구해야 하는 것은
   결국 해당 2차원 배열 A[]에서
   B[k]를 구하는 것이다
   B[k]는 A 배열에서 B[k]보다 작거나 같은 값들이 k개 이상 존재한다는 뜻이다
   (ex : n이 4이고 k가 8인 경우,
   1 2 2 3 3 4 4 4 6 6 8 8 9 12 12 16 이 총 오름차순 배열이고
   이 중 B[8] = 4 이다 (* 참고로 이 문제에선 1부터 센다는 전제가 존재한다))
   
2. B[k]의 low는 1, high는 nxn 이므로 설정
   그리고 mid = (low + high) /2 이므로 반복문을 돌며 설정해준다
   
3. mid의 값보다 작은 것이 A배열에 얼마나 있는지를 세준다
   이 때, A[i,j] = i x j 라는 점을 이용
   i <= n 이므로 각 행에서 mid보다 작은 녀석은 많아도 N개 이며,
   mid를 i로 나누어 줌으로서, 해당 행의 1,2,3,4,5 와 비교가 가능하다(mid / i)
   
4. 개수가 k보다 같거나 큰 경우는 현재 mid의 값이 크다는 의미이니 high를 줄여준다
   k보다 작다면 low를 올려준다
   (같은 경우가 바로 정답은 아니다
   예를 들어 위 경우에서 mid가 5인 경우에도 cnt가 8이 나올 수 있다
   그러나 실제 정답은 4, A 배열 내에 존재하는 값을 구해야 하기에
   low 값을 좁혀나가는 방향으로 작성해야 함)
   
5. while문을 빠져나왔을 때의 low값을 반환한다
   (이러한 방식은 ‘찾고자’ 하는 결과중 ‘최소값’을 반환하는 방식이다
   기본적으로 이진탐색은 ‘찾고자 하는 범위’에 ‘찾는 값’이 반드시 존재할 때 사용이 가능하며,
   이는 low와 high에 각각 ‘조건을 만족하는’ 하한과 상한 을 나타낸다
   결국 A배열의 특정한 요소 보다 작거나 같은 개수가 k개 이상이여야 하는 A 배열의 값이여야 함
   위 예시에서 결국 B[6] = B[7] = B[8] = 4 이며,
   이는 5인 경우에도 k = 8을 만족하지만, 4와 5 중 실제 배열에 존재하는 것은 4이므로
   low를 통해 4를 선택된다)