[G1] 백준 1300번 K번째 수 C++ 이분 탐색, 매개 변수 탐색, Parametric Search

리뷰

 

2차원 배열을 1차원 배열로 옮겨온 후 정렬한 값 중에서 k번째 수를 뽑는 특정 조건을 갖는 이분 탐색 문제 

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

 

문제 풀이

1. n, k값을 받아오고 left를 1, right를 n * n, result를 0으로 초기화 해준다. 해당 타입들은 모두 long long으로 설정
2. left가 right를 넘지 않는 범위 내에서 while문 실행 mid를 left + right를 2로 나눈 몫으로, cnt를 0으로 초기화 해준다.
3. 1부터n까지 탐색하며 mid를 i로 나눈 값을 cnt에 추가해 준다, 이때 해당 값이 n보다 커선 안된다.
4. 탐색을 마친 후 cnt가 k보다 크거나 같으면 right 범위를 mid - 1로, 아니라면 left의 범위를 mid + 1로 바꿔준다.
5. 해당 작업을 반복하다 보면 cnt가 k와 마지막으로 일치하거나 큰 상태가 k번째 값을 구한 상태가 된다.
6. 루프를 종료한 후 left를 출력해 주면 된다.

 

참고 사항

해당 문제를 풀며 작성한 테스트 케이스

1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25

1 2 2 3 3 4 4 4 5 5 6 6 8 8 9 10 10 12 12 15 15 16 20 20 25

1 2 3
2 4 6
3 6 9

1 2 2 3 3 4 6 6 9

 

예제 처럼 n = 3, k = 7일 경우를 보면

left = 1, right = 9인 상태로 시작하게 된다.

mid는 (1 + 9) / 2, cnt = 0

i가 1일때 cnt에는 mid를 i로 나눈 몫과 n중 작은 값이 들어가게 된다, 즉 5와 3중 작은 값인 3이 들어간다.

i가 2일때 cnt에는 2가 들어갈 것이고, i가 3일때 cnt에는 1이 들어갈 것이다.

cnt는 6이 되었고 이는 k보다 작기 때문에 left = mid + 1을 해주고 다시 루프를 시작한다.

 

left = 6, right = 9, mid = (6 + 9) / 2 = 7, cnt = 0

i가 1일때 cnt += 3, i가 2일때 cnt += 3, i가 3일때 cnt += 2

cnt는 8이 되었고 이는 k보다 크거나 같기 때문에 right = mid - 1을 해주고 다시 루프를 시작한다.

 

left = 6, right = 6, mid = (6 + 6) / 2 = 6, cnt = 0

i가 1일때 cnt += 3, i가 2일때 cnt += 3, i가 3일때 cnt += 2

cnt는 8이 되었고 이는 k보다 크거나 같기 때문에 right = mid - 1을 해주고 다시 루프를 시작한다.

 

left = 6, right = 5로 while의 조건문인 left <= right를 만족하기 못하기 때문에 while루프를 종료한다.

이제 left에 저장된 값을 출력해 주면 된다, 정답 6이 출력된다.

 

정답 코드

#include<iostream>
#define ll long long

using namespace std;
ll n, k;

int main() {
	cin >> n >> k;
	ll left = 1, right = n * n;

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