K번째 수 ( 백준 1300 )

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

 

* 처음에 보았을때 이게 왜 이분탐색? 매개변수 탐색? 의문을 가졌던 문제.

* 필자도 잘 정리된 T-Story 글을 보고 이해했으니까 궁금해서 본다면 아래 링크로 이동할 것.

 

* 우선 문제를 이해할 필요가 있을것이다.

 

* 만약 N이 4일때는 A[i][j] = i * j 문제에 따라서 위 같은 값을 할당 받는다

* 두번째로 B[K] 배열도 오름차순으로 정렬해서 위 같은 값을 할당한다

* 문제의 출력값은 B 배열의 K 번째 있는 값을 출력하는 것

* 문제 있는 그대로 구현하면 메모리 초과가 뜨면서 실패하게 될 것이다

 

* 위에 동그라미 되어있는 K=7을 기준으로 설명하면 B[7]는 B 배열에 7번째 있는 값이 4 라는 의미이다

* 거꾸로 설명하면 4(값)보다 같거나 작은 값들이 K개 존재한다는 말도 된다

* 왜냐하면 문제에서 오름차순으로 정렬한 값을 B배열에 할당한 단조증가 배열이기 때문이다

* 즉 모든 구간에서 B[i] <= B[i+@] 가 성립된다

 

* 정리하면 B[K] = x 의 값은 x보다 작거나 같은값이 최소K개 존재한다.

 

* B[10] 을 확인하면 7보다 작은 숫자가 실제로 10개라는 것을 확인 가능하다

* 즉 여기서 이분탐색의 범위를 정의할 수 있다.

* B[K] = x 의 x 값을 조정하면 되는데 그 값의 범위가 최소가 1이고 최대가 K이다

* 위 부분을 이해하는것이 중요하다

 

* 그러면 1부터K의 양끝 값을 기준으로 x값을 조정하면서 좁혀나가면 되지만 결국엔 배열을 할당해야지 가능한것이 아닌가?

 

잠깐 옛날 옛적 구구단을 배웠을 때로 돌아가보자

1단 : {1, 2, 3, 4, 5, 6, 7, 8, 9}

2단 : {2, 4, 6, 8, 10, 12, 14, 16, 18}

3단 : {3, 6, 9, 12, 15, 18, 21, 24, 27}

4단 : {4, 8, 12, 16, 20, 24, 28, 32, 36}

5단 : {5, 10, 15, 20, 25, 30, 35, 40, 45}

6단 : {6, 12, 18, 24, 30, 36, 42, 48, 54}

7단 : {7, 14 ,21 ,28, 35, 42, 49, 56, 63}

8단 : {8, 16, 24, 32, 40, 48, 56, 64, 72}

9단 : {9, 18, 27, 36, 45, 54, 63, 72, 81}

 

* 여기서 각단의 n이하의 숫자를 찾으시오. 하면 어떻게 계산할 것인가

* 1단부터 한땀 한땀 계산할 수도 있지만 ( 찾으려는수 / 구구단의 단수 ) 해주면 찾으려는 수 이하의 갯수를 계산 할 수있다.

 

쭉 나열해보면 다음과 같아진다.

[기준 값 : 8]

1단 : {1, 2, 3, 4, 5, 6, 7, 8, 9}  ->  8/1 = 8

2단 : {2, 4, 6, 8, 10, 12, 14, 16, 18}  ->  8/2 = 4

3단 : {3, 6, 9, 12, 15, 18, 21, 24, 27}  ->  8/3 = 2

4단 : {4, 8, 12, 16, 20, 24, 28, 32, 36}  ->  8/4 = 2

5단 : {5, 10, 15, 20, 25, 30, 35, 40, 45}  ->  8/5 = 1

6단 : {6, 12, 18, 24, 30, 36, 42, 48, 54}  ->  8/6 = 1

7단 : {7, 14 ,21 ,28, 35, 42, 49, 56, 63}  ->  8/7 = 1

8단 : {8, 16, 24, 32, 40, 48, 56, 64, 72}  ->  8/8 = 1

9단 : {9, 18, 27, 36, 45, 54, 63, 72, 81}  ->  8/9 = 0

 

위 논리를 코드로 적용하면.

 

 

* 7이하의 수를 찾기 위해서 

1단은 /1

2단은 /2 

...

해주지만 위 방법은 9x9 전체 구구단의 경우의 수를 반환해주는 것이다.

따라서 문제의 조건에 배열의 범위를 제한하는 N값을 사용해서 몫이 N보다 크다면 N으로 제한해야한다.

 

아래는 구현 코드이고, 내가 참조한 블로그는 아래와 같다.

https://st-lab.tistory.com/281

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

Stranger's님 감사합니다.

코드는 생각보다 간결. 위 논리를 이해하는것이 중요하다.

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

public class BOJ1300 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        binarySearch(N, K);
    }
    private static void binarySearch(int N, int K) {
        int left = 1, right = K;
        while(left <= right) {
            int mid = (left+right)/2;
            if(decision(N, mid) >= K) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        System.out.println(left);
    }
    private static int decision(int N, int mid) {
        int count = 0;
        for(int i = 1; i <= N; i++) {
            count += Math.min(mid/i, N);
        }
        return count;
    }
}

끝.