[백준] 1300번 K번째 수(feat. 이분 탐색 Lower-Bound)

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

1300번: K번째 수

 

문제 접근

이 문제에서 주어진 N의 범위는 10^5, K의 범위는 min(10^9, N^2) 이기 때문에, 
이분 탐색을 이용해야 할 것으로 예상된다.

이 문제를 간단하게 요약하면,
A[i][j] = i*j 이고, 크기는 N*N  2차원 행렬을 1차원 배열 B로 만들 때, B[K]의 값은 무엇인지 구하는 문제이다.
(단 인덱스는 1부터 시작한다. 라고 문제에 제시되어있음)

출처: st-lab

예를 들어 크기가 4*4인 2차원 행렬A를 1차원 행렬 B로 변환하여 B[K]의 값을 찾는 문제이다.
K = 7이라고 한다면, B[7] = 4가 되는 것이다.

그러면 B[K]를 어떻게 구해야할까?

우선, 입력으로 주어질 수 있는 행 또는 열의 크기는 N의 범위인 10^5로 
전체 행렬의 최대 크기는 10^10이다.(100억) 
즉, 브루트 포스로 탐색하기에는 메모리와 시간복잡도 문제가 발생할 수 있다.

브루트 포스 말고 다른 접근 방법을 생각해보아야 한다.

문제의 대략적인 개요와 탐색범위를 고려했을 때는 이분 탐색을 사용해야 한다고 생각이 들지만,
행렬을 생성하는 과정또한 메모리와 시간복잡도 문제가 발생할 수 있을 것이라고 생각된다.

따라서, 행렬을 생성하지 않고 풀이할 수 있는 방법을 고려해 봐야 한다.

문제에서 주어진 것들을 활용해보자.
앞서 예시로 들었던 N이 4로 주어졌을 때,
B[7] = 4 이다. 이말은 즉, "4라는 값보다 작거나 같은 원소의 개수는 최소 7개"라는 의미로 해석할 수 있다.
이것이 가능한 이유는, B행렬은 '단조 증가 행렬' 즉 오름차순 성질을 가지고 있다.
이말은, 모든 구간에 대해 B[i] <= B[i+a] 라는 의미이다.

정리하자면, B[k] = x 라는 의미는 x보다 작거나 같은 원소의 개수가 최소 개 라는 의미이다.

예를 들어 x = 6일때, x보다 작거나 같은 원소의 개수는 몇 개일까?

출처 : st-lab

위 사진에서 볼 수 있듯, 6보다 작은 원소의 개수는 10개임을 확인할 수 있다.
B[K]에서 K는 인덱스가 1부터 시작일 때 K인덱스 까지의 값들 중 B[K]의 원소 값보다 작거나 같은 원소의 개수 라는 의미가 된다.

그렇다면, 우리는 K가 주어졌을 때 B[K]의 값을 구해야 하므로,
B[K] = x일 때, x의 값을 조정해보면서 x보다 작거나 같은 원소의 개수와 입력으로 제공받는 K값이랑 일치할때를 탐색하면 될 것이다.

"x의 값을 조정해나가면서 x보다 작거나 같은 원소의 개수가 K값과 일치"하는 x를 찾으면 된다.
x값은 조정한다고 쳐도, x값에 따른 x보다 작은 원소의 개수는 어떻게 찾아야할까?
결국 행렬을 만들어야 하는 건가?라는 의문이 생길 수 있다.
하지만, 앞서 설명했듯, 행렬을 만들게 되면, 메모리와 시간복잡도 문제가 생길 수 있다.
따라서 행렬을 만들지 않고 탐색을 해야한다.

※구구단을 생각해보자.

1단 : {1, 2, 3, 4, 5, 6, 7, 8, 9}
2단 : {2, 4, 6, 8, 10, 12, 14, 16, 18}
3단 : {3, 6, 9, 12, 15, 18, 21, 24, 27}
4단 : {4, 8, 12, 16, 20, 24, 28, 32, 36}
5단 : {5, 10, 15, 20, 25, 30, 35, 40, 45}
6단 : {6, 12, 18, 24, 30, 36, 42, 48, 54}
7단 : {7, 14 ,21 ,28, 35, 42, 49, 56, 63}
8단 : {8, 16, 24, 32, 40, 48, 56, 64, 72}
9단 : {9, 18, 27, 36, 45, 54, 63, 72, 81}

여기서 "각 단별로 8보다 작거나 같은 수의 개수를 찾아보시오'라고 하면 어떻게 찾을 수 있을까?
물론 1단에서 하나씩 세어보고, 2단에서 하나씩 세어보고..
이렇게 할 수도 있겠지만,
곱셈의 성질을 이해하고 있다면
"8 // n(단) 의 몫 =  n단에서 8보다 작거나 같은수의 값"이라는 것을 알 수 있을 것이다.

예를 들어,
1단은 8 // 1 = 8 즉, 1단에서 8보다 작거나 같은 수의 개수는 8개가 된다.
2단은 8 // 2 = 4로 2단에서 8보다 작거나 같은 수의 개수는 4개가 된다.
3단은 8 // 3 = 2로 3단에서 8보다 작거나 같은 수의 개수는 2개가 된다.

쭉 나열해보면 다음과 같다.
[기준 값: 8]
1단 : {1, 2, 3, 4, 5, 6, 7, 8, 9}  ->  8/1 = 8
2단 : {2, 4, 6, 8, 10, 12, 14, 16, 18}  ->  8/2 = 4
3단 : {3, 6, 9, 12, 15, 18, 21, 24, 27}  ->  8/3 = 2
4단 : {4, 8, 12, 16, 20, 24, 28, 32, 36}  ->  8/4 = 2
5단 : {5, 10, 15, 20, 25, 30, 35, 40, 45}  ->  8/5 = 1
6단 : {6, 12, 18, 24, 30, 36, 42, 48, 54}  ->  8/6 = 1
7단 : {7, 14 ,21 ,28, 35, 42, 49, 56, 63}  ->  8/7 = 1
8단 : {8, 16, 24, 32, 40, 48, 56, 64, 72}  ->  8/8 = 1
9단 : {9, 18, 27, 36, 45, 54, 63, 72, 81}  ->  8/9 = 0

8 + 4 + 2 + 2 + 1 + 1 + 1 + 1 = 20
1단부터 9단까지 중 8보다 작거나 같은 수의 개수 =  20개이다.

 

 

출처 : st-lab

가상의 2차원 행렬 A[i][j] = i*j 을 생각해 보았을 때, 
규칙을 발견할 수 있다. 
위 그림은 N이 4일 때 2차원 행렬의 그림이다.

각 행 혹은 열이 일종의 구구단이 된다.

첫번째 행은 1단, 두번째 행은 2단, 3번째 행은 3단이다.
그러면 N번째 행은 N단일 것이다.

우리는 x보다 작은 원소들의 개수를 찾는 것이 관건인데,
위에서 살펴본 구구단 곱셈의 성질과 각 열or행이 구구단인 2차원 행렬을 이용하면 쉽게 구할 수 있을 것으로 보인다.

예를 들어 n = 4인 경우, x = 3일때,
1단 : 3 // 1 = 3
2단 : 3 // 2 = 1
3단 : 3 // 3 = 1
4단 : 3 // 4 = 0
이다.

x=3 일 때, x보다 작거나 같은 수의 개수는 5개이다.
그리고 5개라는 의미는 K = 5 라는 의미이기도 하다.

출처 : st-lab

결국, 우리는 행렬을 생성할 필요가 없다.
1~N까지 임의의 x로 나눠가면서 해당 합이 K와 같은지 판별하면 되기 때문이다.
이 부분에서 이분탐색을 적용하면 될것이다.

다시한번 정리를 해보면,
B[K] = x 에서 우리가 조정해가며 탐색해야 하는 것은 x이다.
즉, x를 통해 x보다 작은 원소의 개수(=K)를 찾고,
해당 값이 문제에서 입력으로 주어지는 K값과 일치하는지 탐색하는 과정을 이분탐색으로 구현하면 된다.

 

이때, 주의할 점이 3가지 있다.

1. 탐색범위
2. x보다 작은 원소의 개수
3. Lower-Bound

 

[탐색범위]

먼저, 탐색해야할 x의 범위를 생각해보자.
x의 초기 범위는 1~N^2이다.
예를 들어 N = 4라면 x의 초기 범위는 1 <= x <= 16이라는 의미이다.

범위를 더 줄일 수는 없을까?

결론부터 말하자면, 탐색 범위를 줄일 수 있다.

위를 그림을 보면, B행렬에서 x <= K 라는 것을 확인할 수 있다.
K가 가질 수 있는 인덱스는 N^2이하로 한정되어 있고, K의 최댓값은 N^2과 같기 때문에 ,
반드시 x <= K 일 수 밖에 없다.
(위 예시에서 N = 4일 때, K의 최대값은 4 * 4인 16이다. 이는 A[4][4] = 4 * 4로 결국 B[16] = 16으로 x는 N^2이하로 한정되어 있다.

B[K] = x라고 했을 때, x는 항상 K보다 작거나 같다.
즉, x의 범위를 1 <= x <= K 로 좁힐 수 있다.

 

[x보다 작은 원소의 개수]

위에서
x // i단 의 몫 = i단에서 x보다 작거나 같은 수의 개수
임을 파악했다. 하지만 이것을 그대로 x보다 작거나 같은 수의 개수를 구하는데에 사용하기에는 문제가 있다.
"x보다 작은 원소의 개수는 최대 N개를 넘지 못한다"라는점을 고려하지 못하고 있다.

예를 들어 n이 3인 3 *3 행렬일 때를 생각해보자.
각 줄별로 5보다 작거나 같은 값이 몇개 존재하는지 구해보자.
기존 공식대로라면 
첫번째 줄(1단)에서는 5 // 1 = 5개 이어야 한다.
1단 : {1, 2, 3, 4, 5, 6, 7, 8, 9 ..} (5개)

하지만,  n = 3 이므로
행렬의 전체 크기는 3 * 3이다.

해당 행렬의 첫번째 줄 (1단)에서 5보다 작거나 같은 값은
1단 : {1, 2, 3,}  (3개)가 되는 것이다.

따라서, 각 단에서 x보다 작거나 같은 수의 개수는 최대 n개를 넘을 수 없다.

이점을 고려하여 수의 각 단에서 x보다 작거나 같은 수의 개수를 구할 때,
x // i를 사용하면 안되고, x // i 값과 n값 을 비교하여 더 작은 값이 해당 줄에서 x보다 작거나 같은 수의 개수로 사용되도록 해야한다.
min()함수를 이용하여, n*n행렬의 i번째 줄(단)에서  x보다 작거나 같은 수의 개수는  min((x // i), n) 이렇게 이용하면 될 것이다.

 

[Lower-Bound]

이 문제는, 일반적인 이분탐색을 적용하면 안된다.
왜냐하면, 우리가 탐색해야하는 n*n행렬을 1차원 행렬로 정렬한 B행렬에 있는 값은 중복된 값들이 있기 때문이다.

그렇다면, 우리가 고려할 수 있는 것은,
Upper-Bound와, Lower-Bound가 있다.

Upper-Bound는 "찾고자 하는 값을 초과하는 첫 번째 인덱스(혹은 값)을 찾는 것'
Lower-Bound는 "찾고자 하는 값과 같거나 큰 수가 있는 첫 번째 인덱스를 찾는 것'
이다.

n = 4, K = 8 로 주어졌다고 가정해보자.
우리가 이분 탐색에서 분기하는 기준은, 임의의 x보디 작거나 같은 수의 개수와 K를 비교하여 x의 범위를 좁혀나간다.

출처 : st-lab

만약 위와 같이 x 가 4일 때는, x보다 작거나 같은 수의 갯수가 8로 주어진 K값과 같아지게 되면서,
x = 5로 바뀌게 되고, 이분탐색이 종료되어 기존에 이분탐색을 이용해서 풀어온 문제처럼 x-1 를 출력하면 된다.

하지만, x가 5라면 어떻게 될까?

출처 : st-lab

위와 같이 x가 5일 때, 5보다 작거나 같은 수의 개수가 8개인데,
이는 x가  4일 때 5보다 작거나 같은 수의 개수가 8개인 것과 같다.

이문제에, 만약 Upper-Bound를 사용하면, 
Upper-Bound는 "찾고자 하는 값을 초과하는 첫 번째 인덱스(혹은 값)을 찾는 것" 이기 때문에 
n = 4, k =8일 때 4를 반환하지 않고, 6을 반환하면서 이분탐색이 종료될 것이다.

즉,
K값에 대해 x보다 작은 수의 개수가 K값과 같은 경우의 수가 여러개일 가능성이 있기 때문에,
'찾고자 하는 값과 같거나 큰 수가 있는 첫번째 인덱스'를 찾는 Lower-Bound를 사용해야 한다.

 

'''
n * n 배열을 만든다.
초기화를 해야하는데, 배열에 들어있는 수는 A[i][j] = i×j  이다.
그런데 배열의 인덱스는 1부터 시작한다고 가정함.
A[i][j] = (i+1)×(j+1) 이어야 할 것임 .

1 2 3
2 4 6
3 6 9

'''

n = int(input())
k = int(input())
start = 1
end = k

while start < end:
    count = 0
    mid = (start+end) // 2
    for i in range(1, n+1):
        # mid//i단의 몫이 mid보다 작거나 같은 수의 개수라는 공식을 사용하면,
        # 예를 들어 5보다 작거나 같은 값이 실제로 1단에는 5개가 존재하지만, 만약 문제에서 제시된 N이 3이라면 3개만 존재하는 오류가 발생.
        # 이러한 문제점을 고려하여 n값과 mid//i 값을 비교하여 더 작은 값을 count에 더해줘야한다.
        count = count + (min((mid//i), n))
    # mid보다 작은 수가 k값이랑 같은 경우의 수가 여러개일 가능성이 발생하기 때문에 '찾고자 하는 값과 같거나 큰 수가 있는 첫번째 인덱스를 찾는 'Lower-Bound'를 써야한다.
    if count < k:
        start = mid + 1
    else:
        end = mid
print(start)

 

※그림/아이디어 출처 - https://st-lab.tistory.com/