백준 1300 JAVA : K번째 수

문제

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

1300번: K번째 수

 

풀이 예상

NxN 의 최대가 10의 10승이므로 이걸 전부 나열할 수 는 없다고 생각했다.

그래서 규칙을 찾아 보려고 정렬한 숫자를 나열해 보았다.

 

N = 3 인 경우

index	1	2	3	4	5	6	7	8	9
i x j	1	2	2	3	3	4	6	6	9

 

여기서 index 값을 가지고 ixj의 값을 만들거나 ixj의 값으로 index값을 만들어야 해야 하기 때문에 각 index로 ixj가 어떤 관계가 있는지 고민했다.

 

index = 5, ixj = 3 을 보면 

(1~N) x (1~N) <= 3 를 만들 수 있는 경우의 수를 찾는다고 생각해 봤다.

첫번째 부분의 1~N을 i라고 보면

i = 1, 일 때 올 수 있는 두번째 부분의 수는 1~3으로 3개이다.

i = 2, 올 수 있는 두번째 부분의 수는 1밖에 없으므로 1개이다. 

i = 3, 올 수 있는 두번째 부분의 수는 1밖에 없으므로 1개이다. 

=> 이 것을 전부 더하면 5 이므로 딱 index의 값이 나온다.

 

index = 8, ixj = 6 을 보면 

(1~N) x (1~N) <= 6 을 만들 수 있는 경우의 수를 찾는다고 생각해 봤다.

첫번째 부분의 1~N을 i라고 보면

i = 1, 일 때 올 수 있는 두번째 부분의 수는 1~3으로 3개이다.

i = 2, 올 수 있는 두번째 부분의 수는 1~3으로 3개이다.

i = 3, 올 수 있는 두번째 부분의 수는 1~2으로 2개이다.

=> 이 것을 전부 더하면 8 이므로 딱 index의 값이 나온다.

 

이 점을 이용해서 count 한 것과 K와 비교해서 이분탐색을 하면 되겠다고 생각했다.

위 내용의 카운트 식은 아래와 같이 도출할 수 있다.

for (int i = 1; i <= N ; i++) {
	count += Math.min((IxJ의 값)/i , N);
}

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(N*logK)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());
        long K = Long.parseLong(br.readLine());

        long start = 1;
        long end = K;

        while(start <= end) {
            long mid = (start+end)/2;

            long count = 0;
            for (int i = 1; i <= N ; i++) {
                count += Math.min(mid/i , N);
            }

            if(count < K) {
                start = mid+1;
            }else {
                end = mid-1;
            }
        }
        System.out.println(start);

    }
}

 

결과