NN단표

문제

알랩이는 구구단표처럼 NN단표를 만들었다고 한다.

NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.

NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)

알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.

이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다.  

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같은 자연수이다.  

출력

K번째 원소를 출력한다.

 

예제 입력

3

7

예제 출력

6

 

#코드__시간복잡도 탈락

n = int(input()) 
k = int(input()) 
data_list = list()
data_list.append(-1) #0번째 인덱스에 더미 값을 넣어둔다.
 
dan = 1
cnt = 1
 
lastCnt = n*n
 
for i in range(1, lastCnt+1):
  data_list.append(dan*cnt)
  cnt += 1
  if cnt > n: 
    cnt = 1
    dan += 1
 
data_list.sort() 
print(data_list[k])

#코드_개선

n = int(input())
k = int(input())
 
# 1 ~ n*n
# 숫자 p가 몇 번째인가?
 
def getOrder(x):
  # x가 몇 번째인지 반환하는 함수
  '''
  1 2 3 4
  2 4 6 8
  3 6 9 12
  4 8 12 16
  
  12? 12보다 작은 숫자의 갯수 13개 --> 14번째
  '''
  result = 0 # 나보다 작은 숫자들의 갯수
  for i in range(1, n+1):
    if i * n < x: result += n # 맨 마지막의 숫자가 x보다 작다면 전체를 대입
    else:
      if x % i == 0: result += (x//i)-1
      else: result += x//i
  return result + 1 # x가 몇 번째인지를 반환한다.
  
start, end = 1, n*n+1
 
while start+1 < end:
  # start : 항상 정답이 되는 숫자보다 작거나 같은 숫자
  # end : 항상 정답이 되는 숫자보다 큰 숫자
  
  mid = (start+end)//2
  myOrder = getOrder(mid)
   
  if myOrder <= k:
    start = mid
  else:
    end = mid
  
print(start)

 

# 복습

import sys
 
def getOrder(x):
  '''
  1 2 3 4
  2 4 6 8
  3 6 9 12
  4 8 12 16
  
  12? 12보다 작은 숫자의 갯수 13개 -> 14번째
  '''
  # x = 6
  cnt = 0 #나보다 작은 숫자들의 갯수
  for i in range(1, n+1): # 3 : 1 2 3 
    if i*n < x: # x가 행의 맨마지막 수보다 크다는 것은 해당 행의 모든 수보다 크다라는 뜻이다.
      cnt+=n
    else:
      if x%i == 0: 
        cnt += (x//i)-1 # 찾고자 하는 값과 행이 나누어 지면 몫-1 을 더해준다.
      else:
        cnt += (x//i)   # 찾고자 하는 값과 행이 나누어 떨어지지 않으면 몫 을 더해준다.
  return cnt+1 # 해당 값보다 작은 위치가 아닌 해당값의 위치 이므로 +1
 
if __name__ == "__main__":
  input = sys.stdin.readline
  n   = int(input())
  k   = int(input())
  
  start, end = 1, n*n+1
  
  while start+1 < end:
    mid = (start+end)//2
    # 여기에서의 mid의 의미
    # n의 값이 주어질 때
    # 1<=x<n*n+1 의 범위를 갖는다.
    # 이진 탐색 방식으로 해당 값의 위치(k)를 알아내고
    # k값과 비교해 나가면서 k번째의 값을 알아낸다.
    myOrder = getOrder(mid)
    
    if myOrder <= k:
      start = mid
    else:
      end = mid
      
  print(start)