개요

백준 1300번: K번째 수

• 입력
  첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

• 출력
  B[k]를 출력한다.

접근방식

1. N의 크기가 최대 10^5이므로 2차원 배열이나 벡터로 NxN을 짤 순 없다.
   최대 배열 크기가 400억바이트이므로 메모리 초과다.

2. 따라서 NxN의 값들을 저장해놓고 푸는 방식이 아닌
   어떤 값이 몇 번째 값인지 알 수 있도록 구현을 하였다.

3. 이분탐색 방식으로 각각의 mid값이 몇번째 값인지 구하고 K번째 값과 같은지 비교하였다.

4. 구하는 방식에선 각각의 행에서 mid값보다 작은 값이 몇개 있는지 구하였다. (mid/ 각 행의 숫자)

5. 여기서도 백준15732 도토리숨기기 문제와 동일하게 유의사항이 있는데 N이 무한대가 아니라 정해져있는 값이므로 각 행의 끝숫자보다 mid값이 클때는 아래의 방식처럼
   mid/ 각행의 숫자로 갯수를 구하는게 아니라 각행의 끝 숫자 / 각행의 수 를 해야한다.

for (int i = 1; i <= N; i++) {
		//각 행 숫자로 mid값을 나누면 mid보다 작은 값이 몇개 있는지 알 수 있음
		//but, 만약 N이 4인데 mid가 10인경우에 2로 나눴을 땐 2x4에서 끝나는게 아니라 2x5까지 취급하게 되므로 비교해야함
		tmp = min((long long)N*i, mid);
		tmpSum += tmp / i;
		if (tmpSum >= K) return false;
	}

코드

#include<iostream>
#include<algorithm>

using namespace std;
long long N, K;

void input() {
	cin >> N >> K;
}
/// <summary>
/// mid값이 k번째보다 크면 mid줄여야하므로 high값 조절, k번째 보다 작으면 low값 조절
/// </summary>
/// <param name="mid"></param>
/// <returns>mid값이 k번째보다 크면 false, 작으면 true</returns>
bool IsKthNum(long long mid) {
	if (mid > N * N) return false;
	long long tmpSum = 0,tmp=0;
	for (int i = 1; i <= N; i++) {
		//각 행 숫자로 mid값을 나누면 mid보다 작은 값이 몇개 있는지 알 수 있음
		//but, 만약 N이 4인데 mid가 10인경우에 2로 나눴을 땐 2x4에서 끝나는게 아니라 2x5까지 취급하게 되므로 비교해야함
		tmp = min((long long)N*i, mid);
		tmpSum += tmp / i;
		if (tmpSum >= K) return false;
	}
	return true;
}

void solution() {
	long long low = 0, high = 1'000'000'001, mid = 0;
	while (low + 1 < high) {
		mid = (low + high) / 2;
		(IsKthNum(mid) ? low : high) = mid;
	}
	//low출력으로 해버리면 i*j값을 안만족해도 그냥 ㅈ건에 맞으면 출력해버림
	//따라서 만족하는값중에 최소값을 찾아야하므로 high출력으로 변경
	cout << high;
}

int main() {
	input();
	solution();
}

문풀후생

이전 문제인 [백준15732 도토리숨기기]와 비슷한 문제다.
도토리숨기기 문제에서 예외조건 설정에서 좀 데여서 그부분을 신경쓰고 푼 문제다.