백준 1300번 K번째 수 파이썬 풀이

백준 1300번 K번째 수 파이썬 풀이

문제

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

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

---

정답코드

# K번째 수
N = int(input())
K = int(input())

def Binary(start, end):
    while start <= end:     
        mid = (start + end) // 2
        
        cnt = 0
        for i in range(1, N+1):
            cnt += min(N, mid // i)
                
        print(start, end, mid, cnt)
        if cnt >= K: # 줄여야하므로
            end = mid - 1
        else: # 키워야 하므로
            start = mid + 1 
    return start
print(Binary(1, 10**9))

 

 

 

풀이과정

Q) 왜 return end 가 아니라 return start인가?

start 는 가능구간이고 end는 불가능한 구간이다. 우리는 가능 구간을 return해야한다.

예를들어 [1,2,3,(4,5,6),7] 같은 경우에 mid = 5일 때 값이 6이므로 값을 더 키우게 된다.

이후 [1,2,3,4,5,(6),7] 이 되는데 우리는 값이 같거나 큰 경우 end = mid - 1 로 코드를 구현하였다는 것을 생각해보자.

 

 

mid = 6일 때 값이 K보다 크거나 같다면 end는 5인데 5은 6 이고 따라서  K보다 작은 값이므로 return 불가능한 구간이다. 반면 start는 6을 가리킨다. 6은 가능한 구간이다

[1,2,3,4,5),(6,7]

 

start 의 의미를 생각하자. start 는 가능한 구간에  있는 그 임계점 에서의 값이다.

 

Q) 예제 입력 1에서 mid = 5 일 때 값이 6이고 mid = 6일 때 값이 8인데 어떻게 7번째 임을 보장할 수 있는가?

mid = 5 일때  값은 6이다.  조건에 맞는 수가 1,2,2,3,3,4 총 6개이기 때문이다.  일단 위에서 이야기했던 것처럼 5보다 작거나 같은 것의 개수는 6개이다. 따라서 5는 답이 될수 없음이 확실하다. 하지만 임계점에서의 start = 6은 어떨까?

물론 값은 8이지만 이는 1,2,2,3,3,4,6,6 을 모두 포함한 수이다. 6이 여러개가 있어서 7이상의 수가 나온 것이다. 

5는 절대 될 수 없고 6은 7보다 큰 8이 나왔지만, 6의 개수에 의해 초과한 것이므로 7번째 일 수 있음을 보장할 수 있다. 우리가 애초에 그렇게 구현을 한것이다. (포함이므로) 

 

배운점 && 공부방향

1. 이분탐색을 정확히 공부할것.. 그 의미를 생각하며 공부하자.(start end)