[CodeUp/3090] [백준/1300] K번째 수 (Python)

Problem : K번째 수 (codeup.kr), 1300번: K번째 수 (acmicpc.net)

Status : Solved

Time : ?????

 

---

 

문제 설명

 

세준이는 크기가 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]를 출력한다.

 

입력 예시

3

7

 

출력 예시

6

 

 

---

 

풀이

이분 탐색 문제인데, 처음에는 감을 잘못 잡아서 많이 해맸던 것 같다. 이분 탐색 쪽이 약한 것 같으니 쫌 보완해야 싶기도 하다.

 

배열 전체 수를 구하여 계산하는 것은 O(N^2 logN^2)의 시간복잡도가 소요되므로, 무조건 시간 초과가 난다. 따라서 어떠한 규칙성을 통해 시간복잡도를 줄이는 게 우선이 된다.

 

배열은 다음과 같이 생성될것이다.

	1	2	3	4	5	S
1	1	2	3	4	5
2	2	4	6	8	10
3	3	6	9	12	15
4	4	8	12	16	20
5	5	10	15	20	25

이분 탐색 알고리즘은 총 O(NlogN)의 시간복잡도가 소요되므로, 이 문제를 풀기 알맞은 알고리즘이다. 문제는 어떻게 이분 탐색을 적용하냐는 것이다...

 

우선, 임의의 값 S가 몇 번째 위치에 오는지 알고 싶다고 가정하자. 우리는 배열의 각 행에 대해서, S보다 작거나 같은 값들의 개수를 세어볼 수 있을 것이다. S = 6일때를 가정하면,

 

	1	2	3	4	5	S
1	1	2	3	4	5	5
2	2	4	6	8	10	3
3	3	6	9	12	15	2
4	4	8	12	16	20	1
5	5	10	15	20	25	1

 

자세히 보면, 배열의 각 행은 그 행의 idx의 배수 집합임을 알 수 있다. 따라서 S보다 작거나 같은 수의 개수는 그 행의 idx를 나눈 몫이다. 또한 최대 개수는 N을 넘길 수 없으므로, 총 개수는 min(S // idx, N)이 성립한다!

즉 우리는 O(N)의 시간복잡도로 S의 idx 위치를 알 수 있다.  따라서 이 S에 대하여 이분 탐색을 진행하면 되며, 초기 최솟값은 1, 최댓값은 K로 둘 수 있다(K번째 idx에 위치하는 값은 무조건 B[K]보다 작거나 같다!)

 

풀이 코드

N = int(input())
k = int(input())

start, end = 1, k
ans = 0

while start <= end :
  mid = ( start + end ) // 2
  sum = 0
  for i in range(1, N+1) :
    sum += min(mid//i, N)

  if sum >= k :
    ans = mid
    end = mid - 1
  else :
    start = mid + 1

print(ans)

 

풀이 완료!