[BOJ 1300] K번째 수 (Java, 이진탐색)

 

 

---

문제 링크

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

1300번: K번째 수

---

2차원 배열을 1차원으로 이렇게 구할 수도 있다니 또 하나 배운다 :)

 

풀이 

- N (최대 10만), K (10만 ~ 10억)

- N * N 2차원 배열을, 1차원 배열로 변환 후 정렬했을 때 K번째 있는 임의 수를 구하는 문제 

- N이 최대 10만이기 때문에 1차원 배열로 변환시 10^10 = 100억이 되어서 메모리 초과, 시간 초과 발생 가능

 

아래와 같은 연산 방식으로 해서 답을 구하는 방법으로 풀어봄

 

1차원 배열에 K 번째 수를 S라 할때 S보다 작은 숫자가 K개 미만이 되어서는 안됨

=> S보다 작은 수가 K 개 이상이 되는 수 중에 가장 왼쪽에 위치하는 최소값 S(이진 탐색 mid에 해당)을 구하면 됨

 

-> row 이쪽 방향으로 보기	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

 

(입력 예시) N = 3, K = 7 일때

 

L = 1, R = 7 일때 

mid = 4가 되고 

i = 1 일때 Math.min( 4 / 1, 3) = 3; 

i = 2 일때 Math.min( 4 / 2, 3) = 2; 

i = 3 일때 Math.min( 4 / 3, 3) = 1; 

총 6개이므로 6 < 7(K) 가 되어서 L = mid + 1

 

L = 5, R = 7 일때

mid = 6이고

i = 1 일때 Math.min( 6 / 1, 3) = 3;

i = 2 일때 Math.min( 6 / 2, 3) = 2; 

i = 3 일때 Math.min( 6 / 3, 3) = 2; 

총 7개가 되므로 7 >= 7(K) 가 되어서 R = mid - 1

 

L = 5, R = 5 일 때

mid = 5 이고 

i = 1 일때 Math.min( 5 / 1, 3) = 3;

i = 2 일때 Math.min( 5 / 2, 3) = 2; 

i = 3 일때 Math.min( 5 / 3, 3) = 1; 

총 6개가 되므로 6 < 7(K) 가 되어서 L = mid + 1

 

L = 6, R = 5가 되어서 종료

 

기록
- mid / i  의 의미는 row별로 배수를 나타내기 때문에 몫을 구하게 되면 mid 이하의 수가 몇개인지 카운팅 가능 (row 별 최대 개수는 N개)
- 굳이 2차원 배열을 1차원으로 바꾸는 행위를 하지 않아도 연산을 통해 K번째 수를 구할 수 있다고 이해

---

제출 코드

import java.io.*;
import java.util.*;

public class Main {

    static int N, K;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
    }

    static void pro() {
        long result = 0L;
        long L = 1, R = K;
        while(L <= R) {
            long mid = (L + R) / 2;

            long totalCnt = 0;
            for(int i = 1; i <= N; i++) { // row : 1 ~ N 
                totalCnt += Math.min(mid / i, N); // row별 최대 N개 요소 가짐
            }

            if(totalCnt >= K) {
                R = mid - 1;
                result = mid;
            } else {
                L = mid + 1;
            }
        }

        System.out.println(result);
    }


    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}

 

돌아서면 잊어버리고 :0