[BOJ 1300 // C++] K번째 수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1300번 문제인 K번째 수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1300

1300번: K번째 수

문제는 단순하다. index가 1부터 시작하는 N×N 배열의 성분을 각 index의 곱으로 하고, 이 배열의 각 값들을 (중복을 허용하여) 오름차순으로 정렬할 때 k번째 수가 무엇일지 계산하는 것이다.

 

N이 10만까지 가능하기 때문에 직접 모든 값을 계산하여 정렬하는 방식으로는 제한시간 내로 당연히 풀 수 없을 것이다.

 

이 문제를 푸는 요령은 다음과 같다.

 

다음과 같은 문제를 생각하자:

주어진 N×N 배열에 양의 정수 x 이하인 원소는 몇 개가 있는가?

 

이 문제는 수학적 지식을 이용하면 단순하게 풀 수 있다. 자명하게, x가 커지면 N×N의 x 이하 양의 정수의 개수는 같거나 증가한다. 따라서 위 문제를 푸는 함수와 binary search를 이용하여 x 이하의 양의 정수의 개수가 (원래 문제에서 주어진) k개 이하인 정수 중 가장 작은(그보다 큰 수는 배열에 없는 수) 수를 찾으면 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
using std::min;

int counting(int n,int k) { // "작은 문제"를 푸는 함수
    int cnt = 0;
    for (int i = 1;i < n + 1;i++) {
        cnt += min(k / i, n);
    }
    return cnt;
}

int main()
{
    int n, k;
    cin >> n >> k;
    int left = 1, right = k; // n의 제곱으로 해도 되지만 k가 더 작다
    while (left <= right) { // binary search 시작
        int mid = (left + right) / 2;
        int count = counting(n, mid);
        if (count >= k) right = mid - 1; // 양의 정수 mid 이하의 원소개수가 k보다 많거나 같다면 숫자가 더 작은 쪽 범위를 탐색
        else left = mid + 1; // 양의 정수 mid 이하의 원소개수가 k보다 적다면 숫자가 더 큰 쪽 범위를 탐색
    } 
    // left==right의 상황에서 right가 정답보다 1 작은 수라면 left도 정답보다 1 작은 수이고,
    // 마지막에 left가 +1되므로 left는 정답을 가리킨다.
    // left==right의 상황에서 right가 정답을 가리킨다면 left도 정답을 가리키고,
    // 마지막에 right의 값이 -1이 되므로 left는 정답을 가리킨다.
    cout << left;
    
    return 0;
}