문제링크: K번째 수
참고: https://hongcoding.tistory.com/13
다시 이진탐색으로.
너무나도 간단한 방법으로 접근해 보았다.
size = int(input())
index = int(input())
array = []
for i in range(size):
for j in range(size):
array.append((i+1)*(j+1))
array.sort()
print(array[index-1])
당연히 풀릴리 없지ㅋㅋㅋ
메모리 초과가 뜬다.
문제에서 보면 size가 10^5라 array를 만들어서 다 저장하기에는 메모리에 걸린다.
나중에 알게 된거지만, 이렇게 숫자가 터무니 없이 큰 숫자안에서 탐색은 대부분 이분탐색의 신호라고 한다.
보다가 이건 알고리즘을 몰라서 못 푸는 문제가 아니란걸 직감했다.
start와 end는 간단히 일차원 배열의 처음과 끝이라고 예상했는데, mid를 어떻게 update해야 할지 감이 오지 않았다.
구글링을 조금 해보니, 역시나 다른 코어 알고리즘(?)이 하나 들어있었다.
배열안 임의의 값의 인덱스를 알고자 할 때, 값//행 과 사이즈의 최솟값들의 합이 인덱스가 된다.
예를 들자면, 3x3 배열이 있을때 4의 인덱스를 찾고 싶다고 하자.
행 수 만큼 반복하며 최솟값을 누적하면 된다.
4/1 = 4은 사이즈인 3보다 크므로 3이 되고,
4//2 = 2는 사이즈 3보다 작아서 2가 더해지며,
4//3 = 1는 사이즈 3보다 작아서 1이 더해지므로,
인덱스는 6이 되는것이다.
이렇게 일차원 배열에서 4는 6번째에 있다는 것을 알 수 있다.
이를 통해서 mid가 target보다 큰지 작은지 비교가 가능하게 된다.
size = int(input())
index = int(input())
start = 1
end = size * size
while start <= end:
count = 0
mid = (start+end) // 2
for i in range(1,size+1):
count += min(mid//i,size)
if count >= index:
start = mid + 1
else:
end = mid - 1
print(start)
SailingToTheMoooon