파이썬)K번째 수

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

1300번: K번째 수

 

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

start, end = 1, n**2
result = 0

if n**2 == k:
    print(k)
    # k가 n의 제곱이면 당연히 맨 끝자리 수이므로 k를 출력한다.
else:
    while(start < end):
        mid = (start+end)//2

        c = 0
        # mid보다 작거나 같은 숫자 계산
        for i in range(1,n+1):
            c += min(mid // i, n)
        
        if c >= k:
            end = mid
            result = mid
        elif c < k:
            start = mid+1
    print(result)

요점은 k번째 수를 구하는 것이 아닌 mid의 값을 정해 mid값이 k의 수가 되는 것을 찾는 문제이다.

코드를 하나씩 살펴보자

우선 n이 3이라 생각하면 배열은 다음과 같다

1	2	3
2	4	6
3	6	9

무언가 규칙이 보이지 않는가?

각 가로행의 요소는 가로행의 1번째(arr[i][0])의 배수이다.

우선 mid값을 살펴보자.

mid값은 1부터 n의 제곱이 된다.(nxn)

start = 1, end = 9, mid = 5가된다.

여기서 for문으로 c += min(mid // i ,n)을 했는데, 이는 각 행별로 mid보다 작은 값을 찾기 위해서이다.

각 행의 작은 값을 찾았다면 c는 이중배열에서 mid보다 작은 개수(X)가 된다. 즉, 이중배열을 일열로 나열했을 때의 X번째의 수가 된다.