[C++] 백준 1300 k번째 수

문제 링크

---

www.acmicpc.net/problem/1300

1300번: K번째 수

접근 방법

---

 문제를 푸는 과정은 어렵지 않았으나, 문제를 푸는 방법을 떠올리는 것이 어려운 문제였다.

크게 3단계로 나뉜다.

1. 임의의 수 mid를 잡는다.

2. mid보다 같거나 작은 숫자가 갯수 cnt를 찾는다.

3. cnt < k 라면 mid가 더 큰 수여야 한다는 뜻이고, cnt >= k 라면 더 작은 수 이거나 현재 조건을 만족한다는 의미이다. 

 

1번

 과정은 start=1, end=k, mid = (start+end)/2로 잡는다. end = k인 이유는 k보다 작은 숫자는 적어도 k개 보다 많거나 같기 때문이다.

 

2번

 cnt를 구하는 과정이 떠올리기에 어려울 수 있다. 하단의 코드를 보며 차근 차근 따라가보자

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

만약 n=4, mid = 8이라면

1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

이러한 모양일 것이다.

즉, i행은 i*1, i*2, i*3, ..의 숫자들로 이루어져 있고, i행의 숫자들 중 mid보다 작거나 같은 숫자는

(i*j <= m)를 만족하는 j의 개수이고 이는 i*1, i*2, ..., i*j이므로, mid/i와 같은 값이 된다. 하지만 mid/i가 n을 초과할 경우

i행의 cnt=n이 될 것이다.

 

소스 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

long long n, k;

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

long long search() {
	
	long long end = k;
	long long start = 1;
	long long result = 0;

	while (start <= end) {
		
		long long mid = (start + end) / 2;
		long long cnt = countNum(mid); //mid보다 작거나 같은 갯수

		if (cnt < k) {  
			start = mid + 1;
		}	
		else {
			result = mid;
			end = mid - 1;
		}
	}
	return result;
}

int main() {

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

	cin >> n >> k;
	cout << search();
}

개발 환경 : VS2019

질문, 지적 환영합니다!