[Python] 백준 - 1300 K번째 수

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

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

출력

B[k]를 출력한다.

 

 

필요한 도구

 

 

1. 이분 탐색 알고리즘 - 좌, 우측 탐색 : 찾는 값이 없을 경우 가장 근접한 방향의 값을 출력하거나, 찾는 값이 여러 개일 경우에 가장 좌, 우측의 값을 출력한다.

 

 

1) 이 문제의 경우는 좌측 탐색을 기반으로 하는데, 변수가 어떤 의미인지 헷갈리니, 정확히 알아야 한다.

 

 

[Python] 백준 - 1654 랜선 자르기

- 이분 탐색 알고리즘 포스팅 (우측 탐색, 정렬만 바꾸면 좌측탐색과 동일하다.)

 

 

 

문제해결방법

 

 

1. 반복문으로 풀 경우, $O(n^{2})$이고, n이 5,000이상이면 적합하지 않다. 주어진 n의 조건은 $10^{5}$다.

2. 변수의 의미가 중요하다. 코드는 간단한데, 이게 헷갈려서 구글 참조했는데도 이해가 어렵다. 

 

 

1) cnt는 배열 A에서 mid보다 작거나 값은 값이 몇 개있냐는 거다. l , mid, r은 배열 A에 들어있는 k번째 수를 찾는 수의 범위다.

2) k번째수는 k개의 작거나 같은 수의 갯수를 갖는다는 뜻과 같다. 이를 통해 mid가 몇번째 수인지는 알 수 있다.

 

3) n = 4로 가정하면 mid = 1일 때, 1번째수라는 것은 알 수 있고, mid = 2일 때, 3번째 수는 2라는 것은 알 수 있다. mid = 3이면, 5번째 수는 3이라는 것은 알 수 있다. mid = 4이면, 8번째수가 4라는 것은 알 수 있다. 

 

l, r = 0, k # k번째 수는 k보다 작다.
while True:
    if l > r:  # 좌측 탐색으로 r이 l보다 작아지는 순간, 혹은 l이 r보다 커지는 순간 경계가 확정된다.
        return r+1 
    mid = (l+r)//2
    cnt = 0
    for i in range(1, n+1): # mid보다 작거나 같은 수의 갯수
        cnt += min(mid//i, n)

 

 

4) cnt가 k번째 수와 같을 때도, 그 mid값이 k번째수라는 확신은 가질 수 없다. mid가 10일 때도 mid가 9인 경우와 같이 cnt는 13를 내뱉기 때문이다. mid가 9보다 작으면 그 전 숫자인 6까지의 갯수(10개)로 맞춰진다.

이 경우가 있기 때문에 좌측 탐색을 구성하는 것.

 

 

- 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
k = int(input())

def binary(n, k):
    l, r = 0, k
    while True:
        if l > r:
            return l
        mid = (l+r)//2
        cnt = 0
        for i in range(1, n+1):
            cnt += min(mid//i, n)
        if cnt == k:
            r = mid-1
        elif cnt > k:
            r = mid-1
        else:
            l = mid+1

print(binary(n, k))