[맛있는물회] [파이썬] <백준 알고리즘> 1300번 "K번째 수"

문제 조건

---

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

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

 

Input

---

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

 

Output

---

B[k]를 출력한다.

 

생각한 아이디어

---

넘모 넘모 넘모 어렵다.

살짝 DP 문제로 생각했지만 전혀 아니었다.

 

이분탐색이라는 힌트를 얻고도 감도 못잡았다...

 

이 문제의 핵심은 이분탐색이다!

근데 이분탐색에서도 주의해야 할 점이있다.

탐색의 기준값은 mid값보다 작은 수가 몇개가 있느냐 이다.

즉 mid가 6이라 했을때

 

각 값의 배수에서 mid보다 작은 값의 개수를 보는 것이다.

1 ... n

2 4 6 ... 2*n

3 6 9 ... 3*n

...

이 값은 

tmp=0

   for i in range(1,n+1):

      tmp+=min(mid//i,n)

   return tmp

이렇게 셀 수 있다.

 

만약 tmp의 값이 k보다 작다면 front = mid+1로 옮기고

그게 아니라면 rear = mid+1로 해주면서

이분탐색을 진행하면 answer 값을 구할 수 있다.

소스코드

import sys
from collections import deque
from heapq import heappop,heappush
import copy
input=sys.stdin.readline

def check(n,mid):
   tmp=0
   for i in range(1,n+1):
      tmp+=min(mid//i,n)
   return tmp

if __name__ == "__main__":
   n=int(input())
   k=int(input())
   front,rear=1,k
   answer=0
   while rear>=front:
      mid = (front+rear)//2
      res =check(n,mid)
      if res>=k:
         answer=mid
         rear=mid-1
      else:
         front = mid+1
   print(answer)

 

*파이썬 문법 정리