백준 1300 - K번째 수(복습)

문제 링크입니다 https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

K의 값이 주어졌을때, B[K]의 값을 구하는 문제입니다.
N의 값이 최대 10^5이라서 이분 탐색을 하지 않는다면 시간 초과가 나는 문제였습니다.
푸는 방법이 도저히 떠오르지 않아 꾸준함님의 포스팅을 참고했습니다.
https://jaimemin.tistory.com/988

백준 1300번 K번째 수

접근 방법
1. low = 1, high = K로 이분탐색을 시작합니다.
2. mid = (low + high)/2의 값으로 정하고 mid보다 작은 숫자의 갯수를 확인합니다.
3. 1~N까지 for문을 돌려 mid/i의 값과 N값 중에서 작은 값을 cnt에다가 더해줍니다.
4. cnt의 값이 K보다 작다면 low = mid+1로 바꿔줍니다.
5. cnt의 값이 K보다 크다면 high = mid-1로 바꿔주고 result에 mid의 값을 저장해줍니다.
6. 이분 탐색을 마치면 result가 정답입니다.

접근 방법 - 3 설명
B[i] 배열은 A[i][j]의 배열을 오름차순 해서 옮겨 놓은 것입니다.
min(mid/i , N) 은 mid >= i *j 이므로 mid/i가 조건을 만족하는 j의 값입니다. 이를 N과 비교하는 이유는

1*1	1*2	1*3	1*4
2*1	2*2	2*3	2*4
3*1	3*2	3*3	3*4
4*1	4*2	4*3	4*4

A[i][j]가 이런 배열이라고 할때 세로 축을 i라고 하겠습니다.
mid >= i*j임으로 해당 줄에서 mid보다 작은 수의 갯수를 찾으려고 한다면 i로 나눈 값인 j를 더해준다면 각각의 줄에서 작은 값의 갯수를 더할 수 있습니다. 하지만 j의 값이 N보다 클 수 있기에 N보다 크다면 N을 더해주는 것입니다.
예를 들자면 mid가 6입니다. i가 1인 상태에서 j의 값은 6입니다. 하지만 N은 4이기에 한줄에서 mid보다 작은 갯수가 6개가 나올수가 없습니다. 따라서 이때는 최대 갯수인 N을 더해주는 겁니다.
(정말 생각하지도 못할 방법이네요...)

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int N, K;

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    int low = 1;
    int high = K;
    int result = 0;
    while (high >= low) {
        int mid = (low + high) / 2;
        long long int cnt = 0;
        for (int i = 1; i <= N; i++) {
            cnt += min(mid / i, N);
        }
        if (cnt < K) {
            low = mid + 1;
        }
        else {
            result = mid;
            high = mid - 1;
        }
    }
    cout << result;
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!