[Python] BOJ(백준) 1300번 - K번째 수

1. 링크

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

2. 난이도(solved.ac 참고)

골드3

3. 풀이

	n = int(input())
	k = int(input())
	start = 1
	end = k
	ans = 0
	while start <= end:
	mid = (start+end) // 2
	t = 0
	for i in range(1, n+1):
	t += min(mid//i, n)
	if t >= k:
	ans = mid
	end = mid - 1
	else:
	start = mid + 1
	print(ans)

view raw k번째수.py hosted with ❤ by GitHub

처음 봤을 때 골드 3이라는 난이도를 보고서 당연히 쉽게 풀 수 있는 방법대로 풀면 안된다고 생각했지만 그래도 한번 해봤고 역시 메모리 초과가 떴다.

쉽게 풀 수 있는 방법이란 2중 반복문을 돌리면서 [i][j]에 i * j를 넣어주는 것. 그렇게 하면 절대 안된다. 애초에 범위가 10억개였기 때문에 이 문제는 배열을 직접 만들지 않고 풀어야 한다.

 

n * n 배열에서 k보다 작은 수들의 갯수를 구하자. 갯수를 전부 더해준 값을 k와 비교해서 이분 탐색을 진행하면 된다.

5 * 5 배열에서 10보다 작은 수의 갯수를 구하면..

1 * 1 ~ 1 * 5 (10 // 1과 n중 작은 값)

2 * 1 ~ 2 * 5 (10 // 2와 n중 작은 값)

...

이런식으로 진행이 된다. 이는 즉 k를 행의 값으로 나눈 것과 n 중에 작은 값만큼의 개수가 해당 행에서 k보다 작은 수의 개수라는 것이다.

이를 이제 mid에 대해 진행을 해야되는데, mid의 값을 구해나가면서 범위를 축소시켜야 하므로 k가 아닌 mid를 기준으로 개수를 더해나갔다. 그리고 그 뒤에서는 t와 k를 비교한 뒤 그 값에 따라 mid를 조정해주는 방식으로 진행했다.