1300번 - K번째 수

출처: 백준 알고리즘

주소: www.acmicpc.net/problem/1300

1300번: K번째 수

1300번 K번째 수

 

문제 요약: 

 (1) (N, N)인 배열 A을 (1, N²)인 배열 B에 대입

  (1-1) 배열 A[i][j]의 값은 i * j 이다.

 (2) 배열 B를 오름차순 정렬

 (3) 배열 B의 K번째 수를 출력 (단, 배열의 인덱스는 1부터 시작)

 

문제 해결:

 1) 배열 A를 만들어서 배열 B에 대입해서 K번째를 출력하는 방법

   => 처음에는 이렇게 진행하면 쉽게 할 수 있을텐데, 왜 이분 탐색 문제인지를 몰랐다.

   => 하지만, 이렇게 진행하게 되면 많은 양의 메모리가 발생하게 된다.

   => 따라서, 배열을 만들지 않고 배열 B의 K번째 수를 출력해야 하는 방법을 찾아야 한다.

 

 2) 배열 B의 K번째 수를 탐색하는 변수로 계산하여 해당 값을 출력하는 방법

   => 먼저, 간단한 예시를 통해 이해를 해보자.

배열 A

  => 배열 A를 만들면 위와 같다. 이 배열 A를 배열 B로 만들고 정렬을 하면 아래와 같다.

정렬된 배열 B

  => 여기서 K번째 수는 6이다. 

  => 정렬된 배열 B에서 K번째 수라는 것은 1번째 수부터 (k-1)번째 수보다 크거나 같은 수라는 뜻이다.

 

따라서, 2)번으로 푸는 방법의 알고리즘은 아래와 같다.

 

 (1) n과 k를 입력받는다.

 (2) 1 ~ N²만큼 탐색을 진행한다.

  (2-1) 찾고자하는 값의 시작하는 값(start), 마지막 값(end), 중간 값(mid)으로 설정

 (3) start <= end를 만족하는 동안 반복하면서 탐색

  (3-1) 찾고자하는 값이라고 예상하는 중간 값(mid)보다 작거나 같은 값의 개수를 cnt로 설정

  (3-2) cnt < k이면, start = mid + 1으로 설정

  (3-3) cnt >= k이면, end = mid - 1으로 설정하고 cnt와 k가 같을 수도 있기 때문에 정답에 mid값을 저장

  (3-4) mid = (start + end) / 2으로 중간 값을 갱신

 (4) 정답으로 저장한 값 출력

 

  => 여기서, 정렬된 배열 B를 보면 배열 B의 값은 해당 인덱스보다 클 수 없다.

  => 따라서, 탐색을 하는 범위(알고리즘 2번)를 1 ~ k로 한정해도 된다.

 

 

소스 코드:

#include <iostream>
#include <algorithm>
#include <cmath>
 
void solve(int start, int end, int n, int k) {
    int mid = (start + end) / 2;
    int res = 0;
    while (start <= end) {
        int cnt = 0;
 
        // 2차원 배열 A의 값들을 행마다 비교했을 때,
        // mid보다 작은 값이 몇 개가 있는 지 계산// 배열 A의 행을 i로 나눈 값과 mid/i를 비교하는 것과 동일
        for (int i = 1; i <= n; i++) {
            cnt += std::min(mid / i, n);
        }
 
        // mid보다 작은 값의 개수(cnt)가 k보다 작은 경우
        if (cnt < k) {
            start = mid + 1;
        }
        // mid보다 작은 값의 개수(cnt)가 k보다 크거나 같은 경우
        // 같은 경우도 계산하는 경우는 같은 값이 2개 존재하기 때문이다.
        else {
            res = mid;
            end = mid - 1;
        }
        mid = (start + end) / 2;
    }
 
    printf("%d\n", res);
}
 
int main() {
    int n, k;
 
    scanf("%d", &n);
    scanf("%d", &k);
 
    // 1 ~ n^2 만큼 탐색을 진행해야 한다.
    // 하지만, k번째의 수는 k보다 클 수가 없다.
    solve(1, k, n, k);
    
    return 0;
}

한줄평:

-> 정렬된 K번째 수는 앞에 자신보다 작거나 같은 수가 K-1개 있다는 의미로 해석할 수 있다.