[백준 1300번] 파이썬 - K번째 수

백준 1300 - K번째 수

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

# 조건

• 세준이는 크기가 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, N^2)보다 작거나 같은 자연수이다.

출력

• B[k]를 출력한다.

# 접근 방법

• N의 크기가 100,000까지 가능하므로 모든 좌표의 수를 구하는 것은 메모리 초과가 발생한다.
• 이 문제의 핵심을 잘 생각해봐야 했는데 K번째 인덱스의 수가 무엇인지를 찾아야 한다.
  • 즉, k번째 이후의 수는 알 필요가 없다.
• 또한, 배열에 존재하는 규칙을 살펴보면
  • 1행 => 1의 곱셈
  • 2행 => 2의 곱셈
  • 3행 => 3의 곱셈
• 따라서, 임의의 수 t가 존재할 때 1행에는 t // 1개의 t보다 작은 수가 존재하고
  • 2행에는 t // 2개 ...
  • 여기서 주의해야 할점은 N을 넘어가면 안되므로 min(t//1, N) 같이 비교해주어야 한다.
• 이 때, 임의의 수 t가 존재할 때 배열에 존재하는 t보다 작은 값이 k-1개라면 t가 정답이 되는 것이다.
• 이분 탐색을 활용하여
  • left = 0, right = N * N, mid = (left + right) // 2를 해주어 임의의 mid 값을 설정해준다.
  • 1~N까지 임의의 수 // i를 하여 개수를 구해준다.
  • 여기서 구한 개수가 K보다 작다면 left = mid + 1
  • 크다면 right = mid - 1을 해주며 k번째 수를 찾아나가면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

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

left = 0  
right = N*N  

while left <= right:  
    mid = (left + right) // 2  
    cnt = 0  
    for i in range(1, N+1):  
        cnt += min(mid//i, N)  
    if cnt >= K:  
        right = mid -1  
    else:  
        left = mid + 1  
print(left)