[C++] 1300번 K번째 수 - 이분 탐색, 매개 변수 탐색

1. 문제

• N * N 크기의 배열 A[i][j] = i * j이다. 이를 배열 B에 넣으면 크기는 N * N이 된다.
• B를 오름차순 정렬했을 때 B[k]를 구해보자. A, B의 인덱스는 1부터 시작

<입력>

• - 1 - 배열의 크기 \(N(1 \leq N \leq 10^{5}\)
• - 2 - \(k(1 \leq k \leq min(10^{9}, N^{2})\)

<출력>

• B[k]

2. 재정의

• A[i][j] = i *j일때 이들의 오름차순 순서를 구하시오.

3. 해결 방법

• 이 프로그램의 목표는 k번째 숫자인 mid를 찾는 것이다.
• cnt(mid)를 통해 mid 아래에 몇 개의 숫자가 있는지 확인하며 cnt(mid) < k인 경우 매개 변수 탐색을 사용한다고 했을 때 lo = mid+1, cnt(mid) >= k이면 hi = mid-1이다. 이때 결국 lo와 hi는 k번째 수에서 같아지므로 이때 lo를 출력하면 된다.
• cnt(mid)를 구하는 방법은 mid(N, mid/i)이다.

4. 실수한 점, 개선할 점

• 재정의를 할 때 구해야 하는 목표 방향을 잘못 잡아서 오히려 문제를 해결하는데 어려웠다. 재정의는 주관적인 방향을 잡지 말고 객관적으로 정해야겠다는 생각이 들었다.
• k<=10^9이므로 처음 lo는 10^9이 아닌 10^9+1이 되어야 한다.

 

<코드>

#include <iostream>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int MAX_INDEX = 1000000001;

// <문제>
// 배열의 크기 N, 인덱스 k
int N, k;

void input() {
    cin >> N >> k;
}

int f(int mid) {
    int cnt=0;
    for(int i=1; i<=N; i++) {
        cnt += min(N, mid/i);
        if(i > mid)
            break;
    }
    
    return cnt;
}

int solve() {
    // k번째 수
    int res;
    // 이분 탐색
    int lo = 1, hi = MAX_INDEX;
    
    // 매개 변수 탐색
    while(lo <= hi) {
        int mid = (lo + hi) / 2;
        if(f(mid) < k)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    
    return lo;
}

int main() {
    fastio;
    
    input();
    
    cout << solve();
    
    return 0;
}

 

<매개 변수 탐색 1>

https://velog.io/@guswns3371/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%A7%A4%EA%B0%9C-%EB%B3%80%EC%88%98-%ED%83%90%EC%83%89

이진 탐색 & 매개 변수 탐색

 

<매개 변수 탐색 2>

https://m42-orion.tistory.com/70

[C++ Algorithm] 매개 변수 탐색(Parametric Search)

 

<문제 바로가기>

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

1300번: K번째 수

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.