백준 1300[자바] java K번째 수

 

문제 링크: https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

▶문제

 

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

 

▶입력

 

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

 

▶출력

 

B[k]를 출력한다.

 

▶해설 

 

이전에 풀었던 구간 나누기2와 유사하게 풀 수 있습니다. 조건을 살펴보겠습니다. 

 

1. 2차원 배열의 값들은 i*j이다.

2. 1차원 배열의 값은 2차원 배열을 오름 차순으로 정렬한 것이다.

3. 2차원 배열과 1차원 배열의 인덱스는 1부터 시작한다.

 

처음에는 2차원 배열을 만들려고 했습니다. 하지만 주어지는 N의 크기가 커서 시간 초과가 발생할 것 같았습니다. 따라서 일련의 규칙을 찾았습니다.

 

3x3 2차원 배열

{

{1,2,3},

{2,4,6},
{3,6,9}

}

 

위와 같이 있을 때 b[x]에 해당하는 값을 찾을 때 우리는 b[x]보다 작거나 같은 수들의 개수를 x와 비교하면 됩니다.

 

예를들어서 x=4일 때 4 부터 탐색을 진행합니다. 

4보다 작거나 같은 수는 1,2,2,3,3,4 입니다. 개수가 많습니다. 이때 4보다 작거나 같은 수를 4/i로 축약할 수 있습니다. 이유는 i=1~N까지 이므로 x/i에 대한 몫으로 구할 수 있습니다. 여기서 주의점이 있습니다. i=1일 때 N보다 큰 값이 들어온다면 N보다 더 큰 값이 더해집니다. 따라서 아래와 같이 처리를 해줘야합니다. 

 

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

 

이제 left=1, right=m으로 설정합니다. right의 경우 n*n이 최대 수지만 앞 예제에서 봤듯이 m의 값으로 설정해도 무방합니다.

 

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;
import java.util.Arrays;


public class Main {


    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        int m = Integer.parseInt(br.readLine());


        long left = 1;
        long right = m;

        while(left<right){
            long mid = (left+right)/2;
            if(solve(mid)>=m){
                right=mid;
            }
            else{
                left = mid+1;
            }
        }
        System.out.println(left);
    }
    private static long solve(long mid){
        long count=0;

        for(int i=1; i<=n; i++){
            count+=Math.min(mid/i,n);
        }
        return count;
    }
}