백준 1300번 파이썬 문제풀이(K번째 수) - 이분탐색

---

접근 방식을 몰라서 결국 정답을 봤다. 문제의 접근방식은 다음과 같다. 

 

# N이 100일 때
# 1 2 3 1단
# 2 4 6 2단
# 3 6 9 3단
# ...
# 100 200 300 10000 N단

과 같이 존재한다. 

 

만약 여기서 오름차순 후 7보다 작은수가 몇개 있냐 라고한다면

# 7보다 작은 수가 몇개 있냐
# 1 2 3 4 5 6 7 8 9
# 1 3 5 6 6 8 8 8 9 ...
# x x x x x o o o o ... 해당 수의 가장작은 숫자 찾기

위와같이 자기보다 작은수를 저장한다고 치자. 그러면 1은 1개 2는 1의개수 + 2의개수 3은 1의개수+ 2의개수 +3의개수 가 된다. 즉, 다음과 같이 구할수 있으며 이러한 공식을 그대로 이용한다면 다음과 같이 구할 수 있다.

 

# 100 * 100에서 mid = 140 일때
# 1 2 3 4 5 6 ... 100 100개
# 2 4 6 8 10 .... 200 70개
# 3 6 9 12 15 ....300 46개
# ...
# 100 200 300 .. 100 #1개
# 즉 (찾고자하는 값 // i단) 개를 가진다.(단, 해당 단의 전체개수를 넘을 경우 해당 단의 전체개수로 설정)

찾고자 하는 값이 140이라면 140보다 작은 값의 개수는 결국 1부터 N 단중 해당 수를 그 단으로 나눈 값이다. 

 

전체 코드는 다음과 같다.

N = int(input())
K = int(input())

s = 1
e = min(10 ** 9, N * N)
ans = 0


def check(mid):
    total = 0
    for i in range(1, N + 1):
        total += min(N, mid // i)

    return K <= total


while s <= e:

    mid = (s + e) // 2
    if check(mid):
        ans = mid
        e = mid - 1
    else:
        s = mid + 1

print(ans)