[Python]이분탐색 백준 1300

   문제

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

http://wookje.dance/2017/02/20/boj-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98/

설명이 가장 잘되어있는거같다.

위 설명대로 했을때 의심되는부분만 다시 짚어보았다.

초기값 설정문제 right를 N^2을 해야 맞지않는가

이부분은 숫자를 나열해봐도 알수있다. k번째 숫자는 절대 k보다 클수가 없다.

ans값이 배열에 없다면?

우리는 만족하는 값중에 가장 작은값을 찾는다. 그렇다면 그 바뀌는 경계선에서는 그 숫

자가 존재하기 때문에 바뀌는것이다.아래 가져온 설명과 같이 만족하는 최솟값을 찾는

다면 그수는 포함할수 밖에 없다.

아래 설명을 참고했다.

https://www.acmicpc.net/board/view/37110

그러면

1 2 3

2 4 6

3 6 9

를 볼까요?

1 이하의 수는 1개

2 이하의 수는 3개

3 이하의 수는 5개

4 이하의 수는 6개

5 이하의 수는 6개

6 이하의 수는 8개

7 이하의 수는 8개

8 이하의 수는 8개

9 이하의 수는 9개에요.

자 여기서 어떻게 8번째 수가 7,8이 아닌 6임을 알 수 있느냐면..

6을 보면, 6 이하의 수는 8개 이지만, 4 이하의 수는 6입니다. 그러한가요?

그런데 7을 보면, 7 이하의 수는 8개이지만, 6이하의 수 역시 8개입니다. 이 말인 즉슨, 

7은 존재하지 않는다는 겁니다.

8을 봐도 마찬가지입니다. 8이하의 수는 8개이지만, 7이하의 수 역시 8개입니다. 이

 말인 즉슨, 8 역시 존재하지 않는다는 겁니다.

어떠한 수 x가 존재하느냐. 존재하지 않느냐는.어짜피 나오는 수가 정수 집합에 속하기

 때문에 배열에서 나오는 x 이하의 수의 갯수 - 배열에서 나오는 (x-1) 이하의 수의 갯수가

 0인지 아닌지만 보시면 됩니다.

저는 특정 조건을 만족할 때, 조건 하나를 더 따져주는 방식으로 좁혀나갔습니다.

이제 파이썬 코드를 짜보자

N = int(input())
K = int(input())
 
low = 0
high = K#K번째 수는 K를 넘을수 없다.
answer = 0
while low <= high:
    mid = (low + high)//2
    count = 0
    for i in range (1, N+1):
        count = count + min(mid//i, N)#mid//i가N보다 클수 있기때문에 각줄이 N보다 넘게 포함할수는 없다.
 
    if count < K:
        low = mid + 1
    else:#최솟값을 찾아야하기때문에 같을때는 줄여준다.
        answer = mid
        high = mid - 1
 
print(answer)

점점 풀기 어렵고 풀이를 봐도 의문점이 생기거나 이해가 안되는 부분이 늘어나는거 같다.

계속 부족함만 느끼게 된다....