[JAVA] 백준 1300 K번째 수

https://acmicpc.net/problem/1300

1300번: K번째 수

 

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

 

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

 

문제 풀이 

[백준] 1300번 : K번째 수 - JAVA [자바] (tistory.com)

[백준] 1300번 : K번째 수 - JAVA [자바]

 

B[11] = 8

- 8이라는 값보다 작거나 같은 원소의 개수는 최소 11개

- B 행렬은 '단조 증가 행렬'이므로 모든 구간에 대해 B[i[ <= B[i+a]라는 의미 

- B[K] = x라는 의미는 x보다 작거나 같은 원소의 개수가 최소 K개라는 의미

- 7보다 작은 원소의 개수는 6개라는 것을 확인할 수 있음 

- 결국, B[K]에서 K라는 것은 B[K]의 원소 값보다 작거나 같은 원소의 개수라는 의미가 됨 

 

- B[K] = x에서 K인덱스의 원소 값 x를 찾아야 함

- x의 값을 조정해나가면서 x보다 작거나 같은 원소의 개수가 K값이랑 일치하면 됨 

 

- 2차원 배열의 각 칸들의 값은 i*j 형태를 띄므로, 일정한 규칙이 존재 

- 이 규칙에 따르면, 임의의 수 x보다 작거나 같은 수의 개수를 구하는 식이 존재 

 

ex) 3보다 작은 원소의 개수 

- 하나하나 탐색 할 필요 없이 각 단(i)로 나눠버리면 개수가 됨 (구구단 응용)

 

1단 : 3/1 = 3

2단 : 3/2 = 1

3단:  3/3 = 1

4단 : 3/4 = 0

 

총 5개, 즉 x=3에 대하여 x보다 작거나 같은 수의 개수는 5개임을 알 수 있음 

 

- 행렬을 생성할 필요 없이 1~N 까지 임의의 x로 나눠가면서 해당 합이 K와 같은지 판별하면 됨 

 

- B[K] = x에서 조정해서 탐색해야 하는 것은 x이다.

- 즉 x를 통해 x보다 작은 원소의 개수(=K)를 찾고 ,해당 값이 문제에서 주어지는 K값과 일치하는지를 이분 탐색으로 구현을 하면 됨 

 

- x의 범위는 1<=x <= K

- x보다 작은 원소의 개수는 최대 N개를 넘지 못함 

 

////임의의 x에 대해 i번째 행을 나눔으로써 x보다 작거나 같은 원소의 개수 누적합을 구함
///이때 각 행의 원소의 개수가 N(열 개수)를 초과하지 않은 선에서 합해주어야 함 

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

 

 

 

정답 

 

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

public class Main {
    static int N,K;
    static long max,min,mid;
    static long count;
    
    public static void main(String[] args) throws IOException
    {
        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());
        
        //x는 1< = x <= K의 범위를 가짐
        min = 1;
        max = K;
        
        while(min<max)
        {
            mid = (min+max)/2;
            count = 0;
            
            for(int i=1; i<=N; i++)
            {
                count += Math.min(mid/i,N);
                
            }
            
            //count가 많다는 것은 임의의 x(mid)보다 작은 수가 B[K]보다 많다는 뜻
            if(K<=count)
            {
                max = mid;
            }
            else
            {
                min = mid +1;
            }
        }

        bw.write(String.valueOf(min));
        
        bw.flush();
        bw.close();
        br.close();

    }
   
}