[백준][C++] 1300 k번째 수

www.acmicpc.net/problem/1300

1300번: K번째 수

 

 

 

알고리즘 종류

    - 이분 탐색

 

 

 

사고 과정

    1. 1~n*n 범위를 설정한다.

    2. 이분 탐색으로 이 배열에서 mid를 구하고, mid보다 작거나 같은 값의 개수를 배열 A에서 구한다.

        2-1. 구한 개수가 k보다 작으면, left = mid+1을 해준다.

        2-2. 구한 개수가 k보다 크거나 같으면, right = mid -1을 해주고, answer = mid 해준다.

    3. left <= right일 때까지 계속한다.

 

 

 

구현(C++)

#include<iostream>
 
using namespace std;
 
long long num, k;
long long answer;
 
long long count_numbers(long long val){
    
    long long cnt=0;
    
    // 어느 행에서 val보다 작은 숫자의 개수를 찾는 방법
    // val를 행으로 나누어 주면 된다.
    // 단, 1행과 같이 범위를 초과할 수 있기 때문에 min()를 사용한다.
    // 예를 들어, val이 7이고 num이 4이면 개수는 7이 될 수 없므로 4로 해준다. 
    for(int i=1; i<=num; i++)
        cnt += min(num, val/i);
    
    // 전략대로 아래와 같이 하나 하나 i*j를 비교해서 하니 시간초과가 발생했다.
    // 위 방법은 검색을 하여 알게 되었다.  
    //for(int i=1; i<=num; i++){
    //    for(int j=1; j<=num; j++){
    //        if(i*j <= val) cnt++;
    //        else break;
    //    }
    //}
 
    return cnt;
}
 
int main(void){
    
    cin >> num >> k;
    
    long long left = 0;
    long long right = num * num;
    long long mid;
    long long cnt = 0;
    
    while(left <= right){
        
        mid = (left + right) / 2;
        
        cnt = count_numbers(mid);
        
        if(cnt < k){
            left = mid + 1;
        
        // cnt가 k보다 클 때, mid 값이 k번째가 될 수 있어서 answer = mid를 해주었다.
        }else if(cnt >= k){
            right = mid - 1;
            answer = mid;
        }
    } 
    
    cout << answer << endl;
}
 
 

 

 

 

시행착오

    - 정말로 이분탐색으로 푸는 것이 맞는지 의심했다. 보통 이분 탐색이라고 하면, 1차원 배열에서 목표 값과 비교해서 크고 작음으로 위치를 옮긴다. 이 문제는 2가지 요소 때문에 이분 탐색이라고 생각하기 어려웠다.

        1. 도대체 1차원 배열은 어디 있단 말인가? 이분 탐색을 수행할 1차원 배열을 정의할 수 없었다. 이 1차원 배열에 무엇이 들어가야 하는지 생각할 수 없었다.

        2. 목표 값을 무엇으로 정의해야 하는가? 배열 B에서 k번째 요소를 찾는 것이 목표였다. k를 목표 값으로 하면 이분 탐색을 할 배열은 어떻게 정의되어야 하는가? 꼬리에 꼬리를 무는 알쏭달쏭함이었다.

 

    - 30분 정도 전략을 짜보다가 다른 분의 지혜를 빌리기로 했다. 이 블로그에서 위 2가지에 대한 명쾌한 답을 얻을 수 있었다. 

        1. 1차원 배열은 1~n*n까지의 값이 담긴 배열이다. 이 배열 위에서 이분 탐색으로 값을 찾는다. 이 값들은 B[K]를 찾기 위한 후보 값들이다. 어떤 조건보다 값이 작으면 left를 옮기고, 어떤 조건보다 값이 크면 right를 옮겨준다. 결국에 left가 멈추는 위치가 B[k]의 값이다. 이것이 이분 탐색의 과정이다. 어떤 조건은 무엇인가?

        2. 조건은 다음과 값다. 1차원 배열에서 후보 값을 가져온다. 후보 값보다 작거나 같은 값을 2차원 배열인 A에서 모두 찾는다(for문으로 row를 방문). 모두 찾은 개수가 k보다 작으면, 후보 값을 더 크게 해야하기 때문에 left = mid+1를 해준다. 반대의 경우는 right = mid - 1를 해준다. 따라서 목표 값은 k이다. 후보 값보다 작은 값들의 총 개수가 k보다 작은 지 큰 지 확인해야 한다. 

 

    - 관점의 변화 : 보통의 이분 탐색은 찾고자 하는 값을 기준으로 큰 지 작은 지 확인했다. 그러나 여기서는 찾고자 하는 값이 '어떤 값보다 작거나 같은 값의 총 개수'였다. 이렇게 목표 값의 종류을 바꾸어서 다룰 줄 알아야 함을 배울 수 있었다.