[백준] 1300 K번째 수 - JAVA

문제

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

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

풀이

N이 3이라고 해보면 배열 A와 B는 다음과 같습니다.

우리가 찾고자 하는 값은 B[K]입니다. K값이 7이라고 가정하면 위 그림대로 7번째 인덱스를 가지는 6이 정답이 됩니다.
여기서 중요한점은 B배열이 가지는 원소들을 K값에 따라 두가지로 분리해볼 수 있다는 점 입니다.
해당 원소의 인덱스가 K보다 작은 원소들 K보다 크거나 같은 원소들 이렇게 두개의 그룹으로 나타낼 수 있습니다.
즉 이분탐색을 이용해 풀 수 있다는 소리가 됩니다.
이분탐색시 사용할 parameter는 B배열의 원소값이 됩니다. 원소값을 이용해 해당 원소값이 B배열에서 몇번째로 위치하는지 구한후 구한 값이 K보다 작다면 low = mid가 되게하고, K보다 크거나 같으면 high = mid가 되게합니다.

그렇다면 해당 배열의 원소가 몇번째에 위치하는지 어떻게 알 수 있을까요?? 먼저 B의 원소값들은 ij라는 것을 알고 있어야 합니다.
N이 3일때 ij로 원소값을 표현한다면 다음과 같습니다.

1*1 1*2 1*3
2*1 2*2 2*3
3*1 3*2 3*3

여기서 각 행을 주목해 봅시다. 일단 i=1일때를 봐보면

1*1 1*2 1*3

무언가 보이지 않나요?? 바로 구구단에서 1단의 형태입니다.
i=2일때도 봐보면 역시 구구단의 2단인걸 알 수 있습니다.그럼 각 행은 구구단이 되는건데, 이것과 원소의 위치는 도데체 무슨 상관이길래 그러는 걸까요??

각 단 별로 어떤 값보다 작거나 같은 수의 개수를 구할 수 있기 때문입니다.
각 단별로 4보다 작거나 같은 원소의 개수를 구하라고 하면 다음과 같이 구할 수 있습니다.
1단: {1,2,3,4,5,6,7,..} 4/1 = 4
2단: {2,4,8,..} 4/2 = 2
3단: {3,6,9,12..} 4/3 = 1
즉 구할 원소 / 단 으로 각 단 별로 해당 원소보다 작거나 같은 수를 구할 수 있습니다.
이것을 함수로 작성하면 다음과 같을겁니다.

static public boolean check(int mid) {
    int count = 0;
    for(int i=1; i<=N; i++) {
      count += Math.min(N, mid / i);
    }
    return count < K;
}

count += Math.min(N, mid / i);를 한 이유는 만약 N = 3일때 5보다 작거나 같은 수를 구한다고 하면
1단: {1,2,3,4,5,6,7,..} 5/1 = 5
2단: {2,4,8,..} 5/2 = 2
3단: {3,6,9,12..} 5/3 = 1
이렇게 구할 수 있습니다, 하지만 N=3이니 1단에서 나올 수 있는 최대값은 3이 됩니다. 그래서 위와 같은 방식으로 예외를 처리해 줬습니다.

이제 이분탐색의 low와 high의 범위를 알아내면 됩니다. 당연히 될 수 있는 최댓값은 N^2이 됩니다. 하지만 이마저도 범위를 좁힐 수 있습니다.
K가 가질 수 있는 인덱스는 N^2안에서 한정되어 있고, K의 최댓값은 N^2ㄱ과 같기 때문에
우리가 찾는 원소를 x라 하면 x <= K일 수 밖에 없게 됩니다.
즉, 1 <= x <= K로 범위를 정할 수 있습니다.

코드

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

public class BOJ_1300 {
  static int N,K;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    K = Integer.parseInt(br.readLine());
    int low = 0;
    int high = K;
    while(low + 1 < high) {
      int mid = (low + high) / 2;
      if(check(mid)) {
        low = mid;
      }else {
        high = mid;
      }
    }
    System.out.println(high);
  }
  static public boolean check(int mid) {
    int count = 0;
    for(int i=1; i<=N; i++) {
      count += Math.min(N, mid / i);
    }
    return count < K;
  }
}