[BOJ 1300 / 파이썬]K번째 수

0. 문제 링크

https://www.acmicpc.net/problem/1300

1. 문제

2. 사용 알고리즘

이분탐색

3. 해결 방법

처음 이 문제를 해결하려 할 때 1부터 K번째 수까지 세는 것은 100% 시간 초과가 날 것이다.

왜냐하면 K의 값이 10^9까지 올라 갈 수 있기 때문이다.

그러므로 처음에는 i, j 번째의 숫자의 특성이 있나 파악했다.

3 * 3 배열 ( N = 3 ) 일 때 다음과 같은 특성을 알 수 있었다.

1	2	3
2	4	6
3	6	9
1의 배수	2의 배수	3의 배수

조금 더 세밀하게 이야기 하면 특정 숫자의 이하의 숫자 배열은 다음과 같다.

N = 7의 예시를 들어보겠다.

18 숫자보다 작거나 같은 숫자는 다음과 같다.

배열이 크다면 파랑색 부분(8)도 포함되겠지만 배열 밖이므로 예외이다.

count = 0
for i in range(1, N + 1):
	count += min(NUMBER // i, N)

위의 초록색 타일의 개수를 얻는 코드이다.

각 A번째 열은 A의 배수임의 특징을 살린 것이다.

2열을 예를 들어보자,

[2의 배수 16, 18]은 18 보다 작거나 같다. 하지만 이 배열의 최대 크기는 7이다.

그러므로 count += min(NUMBER// i, N) 에서 N이 들어가는 이유이다.

4행을 예를 들어보자,

분명 25, 30, 35는 5의 배수이다. 배열 속 숫자 [ 25 30, 35 ]는 18보다 작거나 같지 않다..

그러므로 count += min(NUMBER// i, N) 에서 NUMBER // i 가 들어가는 이유이다.

 

배열 속에서 특정 숫자보다 작거나 같은 숫자의 개수를 얻는 방식을 이용해서 이분탐색을 하면 된다.

4. 코드

import sys

input = sys.stdin.readline


def main():
	N = int(input())
	K = int(input())
	
	left = 1
	right = N * N
	
	while left <= right:
		mid = (left + right) // 2
		
		count = 0
		for i in range(1, N + 1):
			count += min(mid // i, N)
		
		if count >= K:
			right = mid - 1
		else:
			left = mid + 1
	
	print(left)


main()

여기서 아래의 3 * 3의 배열을 예시로 든다면, 아래의 배열에 5의 숫자는 없다.

1	2	3
2	4	6
3	6	9

그렇기에 [4이하의 숫자 개수] = [5이하의 숫자 개수] 이다. 그러므로 

특정 숫자 A ~ B 이하의 숫자 개수가 동일하다면, 문제 조건대로 A가 출력되야 할 것이다.