백준 1300 : K번째 수

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

1300번: K번째 수

[ 문제풀이 ]

N이 최대 100000이기 때문에 모든 수를 구해서 정렬한다면 TLE가 발생할 것이다.

이를 현재 숫자가 key라고 할때, key 보다 작거나 같은 수가 k개 이상인지를 판단하는 결정 문제로 변환하여 파라메트릭 서치를 활용하면 해결할 수 있다.

이때 주의해야할 점은 구한 수가 key랑 같다고 끝내버리면 안 된다. 왜냐하면 현재 수인 key가 실제 존재하지 않는 수일 수가 있기 때문이다.따라서 같은 경우에도 left를 변경해줘야 한다.

 

key보다 작거나 같은 수를 구할때 이중 for문을 통해 구한다면 TLE가 발생할 것이다.

이는 각 배열에 있는 수는 ixj이라는 특성을 잘 생각해보면 쉽게 구할 수 있다.

1행에는 1x1, 1x2, ... , 1xN의 수가 만들어진다. 이들은 모두 1이라는 공통 약수를 가진다. 즉, key를 1로 나눴을 때의 수가 1행에 key보다 적거나 같은 수를 의미한다.

다만, 개수가 N보다 클 경우도 존재하는데 최대값은 열의 수인 N인 점만 주의해주면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int N, k;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			N = Integer.parseInt(br.readLine());
			k = Integer.parseInt(br.readLine());
			int l = 1, r = k;
			while (l <= r) {
				int m = (l + r) >> 1;
				int count = getCount(m);
				if (count >= k) r = m - 1;
				else if (count < k) l = m + 1;
			}
			bw.write(l + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int getCount(int key) {
		int count = 0;
		for (int i = 1; i <= N; ++i) {
			count += Math.min(key / i, N);
		}
		return count;
	}
}