K번째 수

출처 : 백준 #1300

시간 제한	메모리 제한
2초	128 MB

---

문제

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

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

---

입력

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

---

출력

B[k]를 출력한다.

---

입출력 예시

예제 입력 1

3
7

예제 출력 1

6

---

풀이

생각

• 우선 이차원 배열을 만들어 리스트 B의 k번째 인덱스를 직접 구하는 것은 메모리 초과가 될 가능성이 높다.
• N이 10^5보다 같거나 작기 때문이다.
• 따라서 직접 이차원 배열을 구현하지 않고, 인덱스 k에 해당하는 값이 무엇이 올지 예측해야 한다.

풀이 설명

• 이를 위해서는 이분탐색을 이용하게 되었다.
• 예를 들어 mid = (start+end)//2 라고 했을 때, mid 이하의 숫자가 몇 개인지를 어떻게 알 수 있을까?
  • B에는 ixj의 값이 들어간다. -> 일정한 규칙이 존재
  • 이 규칙에 따르면, 임의의 수 a보다 작거나 같은 수의 개수를 구하는 식이 존재한다.
  • 각 행은 구구단처럼 1,2,3단.. 식으로 나타나기 때문에 (a/행번호)가 그 행에서 구하고자 하는 개수가 된다.
  • 단, (a/행번호)가 N보다 클 경우에는 N이다.
    • ex. a = 4일 때, 4/1 = 4이지만, N = 3이라면, 3열까지만 존재하므로 3개라고 볼 수 있다.
• 이렇게 temp라는 변수에 mid 이하의 수들의 개수를 모은다.
• temp와 k를 비교
  • temp >= k라면, end 값을 mid-1로 업데이트 한다.
  • temp < k라면, k까지 오지 못했으므로, start 값을 mid+1로 업데이트 한다.

python code

# 백준 1300번
from sys import stdin
def solution(n, k):
    start = 1
    end = k
    while start <= end:
        mid = (start+end)//2
        temp = 0
        for i in range(1, n+1):
            temp += min(mid//i, n)
            
        if temp >= k:
            answer = mid
            end = mid - 1
        else:
            start = mid + 1
    return answer

n = int(stdin.readline())
k = int(stdin.readline())
print(solution(n, k))