[이분탐색] K번째 수(1300)(C++)

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

1300번: K번째 수

 

1. 문제 개요

 

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

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

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

다음과 같이 2차원 배열에 들어있는 원소의 값이 인덱스의 곱(ixj)일때, 이 이차원 배열의 원소들을 일렬로 나열했을 때 K번째에 오는 원소의 값을 구하는 문제이다. 예를 들어, 3x3 배열을 일렬로 나열했을 때 7번째에 오는 수는 6이 된다.

 

 

이 문제는 이분탐색으로 풀 수 있다. 1부터 N*N 까지의 수를 탐색범위로 잡고, mid 이하의 수가 배열에 몇 개 들었는지 탐색함으로써 풀 수 있다.

 

예를 들어 N=3, K=7 인 경우에,  left 값은 1, right 값은 9로 초기에 설정된다.

이때의 초기 mid 값은 5가 되므로 5 이하의 수가 배열에 몇 개 들어있는지를 세어본다. 6개가 들어있는데 이 값은 목표값인 K보다 작으므로 검색 범위를 6-9로 좁힌다. 이런식으로 반복하게 되면, 7번째 수가 6이라는 것을 알 수 있다.

 

 

이런식으로 이분탐색을 진행하면 정답값을 찾을 수 있다. 그렇다면 배열에 mid 값 이하의 수가 몇 개 들었는지 찾는 알고리즘이 필요하다.

이는 배열에 들어있는 수가 i*j 임을 이용하여 해결할 수 있다.

 

 

만약 3보다 작은 수를 모두 구한다고 하면, 첫번째 열에서 3개, 두번째 열에서 1개 세번째 열에서 1개가 들어있음을 알 수 있다.

그렇다면 3/1 + 3/2 + 3/3 과 같은 식으로 구할 수 있음을 알 수 있다.

 

그러나 6에 다음과 같은 수식을 적용하게 되면, 6/1 + 6/2 + 6/3 = 11개로 맞지 않음을 알 수 있다. 6/1값이 하나의 열에 있는 최대 원소의 개수는 N을 넘기 때문이다. 따라서 max(3,6/i), i=1..N 과 같은 수식으로 최대값을 벗어나는 것을 방지할 수 있다.

 

 

4. 전체 코드

 

#include <iostream>

using namespace std;

int main(void) {
    long long N, K;
    scanf("%lld%lld",&N,&K);
    
    long long left = 1, right = N*N;
    
    while(left<=right) {
        long long mid = (left+right)/2;
        long long sum = 0;
        for(int i=1;i<=N;i++) // mid 값 이하의 원소의 개수를 구한다.
            sum += min(N,mid/i);
        if(sum>=K)
            right = mid-1;
        else
            left = mid+1;
    }
    
    printf("%lld\n",left);
    
}

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!