b1300. K번째 수

 

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

 

 

 

이문제를 처음 접했을 때 int[][] 배열에 모두 채워넣은뒤

그 수들을 int[] 에 집어넣고 이분탐색을 통해 풀어야 하나 라는 생각을 갖게되었다.

하지만 조건중 N의 범위가 100000임을 알게되었고 이방법은 안되는 것을 깨닫고 

열심히 노가다를 시작

 

 

 

열심히 메모장에 적어가며 공식이나 규칙을 발견하려 하였지만

생각해낸건 '구구단인데? ' 까지였고

 

다른 블로그의 도움을 받아 이분탐색을 활용한 풀이법에 도달할 수 있었다.

 

우선 내가 알고있던 이분탐색은 

오름차순으로 정렬된 배열에서 

left 와 right를 활용하여 mid를 선정하고

mid값과 목표값을 비교하여 작다면 right는 mid-1이 되고

크다면 left가 mid+1이되어 값을 찾아나가는 방식이었다.

 

하지만 이는 반대로 mid를 통해서 값을 유추해나가는 역순의 방법을 통해 풀이될 수 있었다.

 

이 역순의방법을 이해하기 위해서는 규칙이 이해되어야한다.

바로  N×N 배열에서 값의 순서를 결정하는 방식이다.

 

배열의 각 위치는 (i,j)에서 i×j로 계산되며,

이를 일종의 "구구단"처럼 구성된 배열이라고 볼 수 있다.

이 배열은 단조 증가의 특성을 가지며,

특정 값보다 작은 숫자가 몇 개인지 빠르게 계산할 수 있는 규칙을 이용해 문제를 푼다.

우선, M번째 작은 수를 찾기 위해 이분탐색을 적용한다.

이분탐색의 핵심은 단순히 값을 찾아가는 것이 아니라,

"중간 값(mid)이 몇 번째로 작은지"를 계산해 그 위치를 기반으로 탐색 범위를 조정하는 방식이다. 이 역순의 접근은 문제를 단순히 값 비교가 아닌, 위치를 중심으로 해결하도록 도와준다.

탐색의 범위는 1부터 M까지로 설정한다.

각 단계에서 mid 값을 계산한 후, 해당 mid 값보다 작은 숫자의 개수를 cnt로 누적한다. 
cnt를 계산하는 방법은 규칙에서 알 수 있듯이, 배열의 각 행에 대해 mid/i로 나눴을 때 
N보다 작은 값을 누적하는 것이다. 이 계산은 한 줄씩 최대 
N번 반복되므로 효율적이다.

만약 cnt가 M보다 작다면, 현재 mid 값은 우리가 찾는 값보다 작다는 의미로 

left를 mid+1로 이동한다. 

반대로 cnt가 M 이상이면, mid 값은 우리가 찾는 값 이상이므로 right를 mid-1로 이동하고, 현재 mid 값을 잠정적으로 정답 후보(answer)로 설정한다.

탐색이 끝나면 answer에는 M번째로 작은 값이 저장되어 있고, 이를 출력하면 된다.

이 문제는 이분탐색의 응용을 통해 "값이 위치를 결정하는 방식"이 아니라

"위치에서 값을 추론하는 방식"으로 문제를 해결하는 문제였다.

 

 

 

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

public class b1300 {

    static int N, M;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        int answer = 0;
        int left = 1 , right = M;
        while(left<=right){
            int mid = (left+right)/2;
            int cnt = 0;
            for(int i = 1 ; i <= N ; i++)
                cnt+= Math.min(mid/i,N);
            if (M > cnt){
                left = mid+1;
            }else{
                right = mid-1;
                answer = mid;
            }
        }
        System.out.println(answer);
    }
}