[1300] K번째 수

K번째 수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1076	318	219	36.139%

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

출력

k번째 원소를 출력한다.

예제 입력 

3
7

예제 출력 

6

힌트

　　　　　　　　　　　　　　　　　　　　　

너무 어려워서... 블로그 돌아다니면서 공부했습니다...

사실 아직도 정확히 이해가 안가네요...

의문점 1.. return값이 왜 left일까요...

cnt >= k 같을 경우 mid를 임시로 저장해서 끝까지 탐색한 다음 임시로 저장한 값을 출력하는 건 이해가 가는데

left가 결국 결과값이 되는 부분은 이해가 안가네요.

의문점 2.. 어째서 right에 n^2이 아닌 k를 넣는건지 잘모르겠습니다..

음.. 당연히?? k가 내가 찾는 수 보다 크기 때문에 불필요한 탐색을 줄이기 위함일까요????

세번째 의문... 이 방법을 어떻게 사람들은 생각한걸까요.. 천재일까요 T__T..머리가 너무 부럽네요..

처음에 if(cnt == k) return mid;가 왜 아닌가에 대해서 고민했는데...

i*j로 표현할 수 없는 수가 있을 수 있다고 하는데... 이것 또한 어떻게 ..생각하는 걸까요..후..

아참... 이분탐색에서 for문을 돌리는 이유는 mid값보다 작거나 같은 수를 체크하기 위함입니다.

mid / i와 n의 크기를 비교해서 작은 값을 쓰는 이유는 예를들어 n이 4라면 테이블이 아래처럼 만들어질 것입니다.

 1  2  3  4

 2  4  6  8

 3  6  9 12

 4  8 12 16

mid가 만약 6이라면 i == 1일 때 n = 4와 6 / 1 을 비교하게 됩니다.

하지만 1의 배수 중에 가장 큰 수는 4이므로 6개가 될수 없습니다.

그렇기 때문에 1의 배수 중에서 6보다 작은 수는 4개가 되겠죠.

마찬가지로 i == 2일 때 2의 배수에서도 6보다 작거나 같은 수를 찾습니다.

6/2를 하면 2, 4, 6이 포함되는 3이되겠죠.. 그렇게해서 3개

i == 3일 땐 같은 방법으로 3, 6을 포함한 2개

i == 4일 때는 4를 포함한 1개입니다.

총 카운트는 4 + 3 + 2 + 1 = 10 입니다.

이렇게 함으로써 mid보다 작은 수의 갯수를 셀 수 있습니다.

완벽히 이해는 못했지만 코드는 올리겠습니다.

#include <stdio.h>
#include <algorithm>
 
int n, k;
 
int binary_search(int left, int right)
{
    if(left > right) return left;
 
    int mid = (left + right) / 2;
    int cnt = 0;
 
    for(int i = 1; i <= n; i++) cnt += n > mid / i ? mid / i : n;
 
    if(cnt < k) return binary_search(mid + 1, right);
    else return binary_search(left, mid - 1);
}
 
int main()
{
    scanf("%d %d", &n, &k);
 
    printf("%d", binary_search(1, k));
 
    return 0;
}

dotorya 

1. return값이 Left가 된다는 부분 자체는 사람들마다 구현이 다르기 떄문에.. 굳이 큰 의미를 둘 이유는 없다고 생각합니다.

저도 다른 분들의 이분탐색 코드를 읽을 때는 시간이 좀 걸리는 편입니다.

다만, "cnt >= k인 가장 작은 숫자"를 탐색하고 있다는 사실만 잘 염두에 두고 코딩하신다면 문제 없을 거라고 생각합니다.

2. 생각하신 것이 맞는 것 같습니다.

추가로 N*N을 기준으로 탐색하면 long long 변수를 써야하는 귀찮음도 있을 것 같습니다.

* 여기에 더해서 드리는 말씀인데, 위 코드에서 cnt 변수에 overflow가 발생할 가능성이 없을지는 한번 확인해보시는게 좋을 것 같습니다.

아마 발생하지 않을 것 같긴 한데, 명확하게 증명해 보는게 좋겠죠..

3. 이런 방법을 처음 볼 때는 아마 누구라도 생각하기 어려울 것 같습니다.

이 문제처럼 답을 정해놓고 그 답이 가능한지 이진탐색하는 종류의 문제들을 Parametric Search라고 합니다.

사람들이 이 문제를 잘 생각하는 건, 어떻게 보면 이런 종류의 문제가 수십개씩 있었기 때문이라고도 생각되네요.

다음에 이런 문제가 나왔을 때 이 아이디어를 떠올릴 수만 있으면, 그것만으로도 잘 배우신 것이 아닐까요?

결국 그런 지식들과 응용할 수 있는 능력들이 모여서 실력이 쌓이는 거라고 생각합니다.