[백준 1300] K번째 수 [C]

백준 - 1300

---

풀이

i * j로 구성된 N x N크기의 배열의 수들을 작은 오름차순으로 나열했을 때, K번째 수가 무엇인지 알아내는 문제다.

N = 3, K = 7일 때, 

K번째 수는 다음과 같다.

K	1	2	3	4	5	6	7
i*j	1	2	2	3	4	4	6

 

즉 임의의 수 mid에 대해 i*j <= mid 만족하며,각 행(i)에서 열(j)들의 개수가 K와 일치할 때까지 탐색하면 된다.

단, 열(j)의 개수는 N을 초과할 수 없다.

for (int i = 1; i <= N; i++)
    cnt += min(N, mid/i);

---

소스코드

#include <stdio.h>
#define min(a,b) a < b ? a : b
int main(){
    int N, K;
    scanf("%d %d", &N, &K);
    int first = 1, last = K;
    while (first <= last){
        int mid = (first+last)/2, cnt = 0;
        for (int i = 1; i <= N; i++)
            cnt += min(N, mid/i);
        if (cnt < K) first = mid + 1;
        else last = mid - 1;
    }
    printf("%d", last+1);
}

---

출처

1300번: K번째 수