문제
구구단표처럼 NN단표를 만들었다.
NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.
NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)
알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.
이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다.
입력
첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같고, 10,000,000,000보다 작거나 같은 자연수이다.
출력
K번째 원소를 출력한다.
예제 입력
3
7
예제 출력
6
풀려고 고민하다가 도저히 문제풀 방법이 생각 나지 않아서 검색해서 풀었던 문제다. N 을 입력 받았을 때 N*N 구구단표에서 K번째 작
은 수를 찾는 문제인데, 푸는 방법을 보고 공부하면서 어떻게 이런 방법을 생각할 수 있을지 신기하기도 하고, 이정도 문제를 풀려면 얼마나 공부를 많이 해야 하는지 실감하는 문제였다.
예시를 한번 들어보면 N의 입력을 6을 받아서 6*6 구구단표를 만들었다고 생각해보자.
1 |
2 |
3 |
4 |
5 |
6 |
2 |
4 |
6 |
8 |
10 |
12 |
3 |
6 |
9 |
12 |
15 |
18 |
4 |
8 |
12 |
16 |
20 |
24 |
5 |
10 |
15 |
20 |
25 |
30 |
6 |
12 |
18 |
24 |
30 |
36 |
만약에 여기에서 18보다 작거나 같은 수의 개수를 찾아보자.
1. 18을 1행의 첫번째 숫자들 (1~6)로 나누고 나머지는 버리게 되면 나오는 답은 18 9 6 4 3 3 이다.
2. 6*6 단표이므로 18 9 6 4 3 3 에서 6보다 큰 숫자들을 6으로 바꾸게 되면 6 6 6 4 3 3 이다.
3. 그리고 6 6 6 4 3 3 을 모두 더하게 되면 각 숫자에 해당하는 열에서 18보다 작거나 같은 숫자가 몇개 있는지 나오게 된다.
4. 1열부터 6열까지 18보다 작거나 같은 숫자의 개수를 다 더하게 되면 6+6+6+4+3+3 = 28 개가 나온다.
이러한 방법으로 이진탐색을 하여, 1부터 N*N 까지 이진탐색을 하여 mid 값보다 같거나 작은 숫자의 개수를 구하여 만약에 그 값이 구하는 K의 값보다 작게 되면 mid+1 부터 end 까지 이진탐색을 다시 수행하고, 그 값이 K 값과 같거나 크게 되면 ans 변수를 선언하여 ans와 mid를 비교하여 mid가 더 작으면 ans에 mid를 저장하고, 아니면 다시 start부터 mid-1까지 이진탐색을 수행 하면서 범위를 좁혀가면서 답을 구하게 된다. K 번째로 작은 값은 같은 숫자가 여러개 중복되어 있기 때문에, 정확히 몇행 몇열에 있는 숫자가 K번째로 작다고 말할 수 없다. 그래서 이진탐색으로 mid보다 작은 값들의 개수를 각 열에서 더하여 K 보다는 같거나 크지만 그 중 최솟값 mid를 정답으로 선택하는 것이다.
여기서 주의할점은 N은 100,000보다 작은 수 이기 때문에 int로 선언해도 되지만, N*N를 받는 매개변수나, K값의 범위는 10,000,000,000 이기 때문에 long으로 선언해줘야 한다.