[백준] 1300번 - K번째 수 (이분 탐색) - 결과 포함

www.acmicpc.net/problem/1300

1300번: K번째 수

이 문제도 파라메트릭 서치 유형의 이분 탐색 문제이다.

이 문제도 해결 방법이 쉽게 떠오르지 않아 다른 사람들의 설명을 많이 참고했다.

해설을 들어도 바로 이해가 되지 않아서 예시를 하나 하나 따라가보면서 이해하려고 노력했다.

 

이해하고 코드를 작성하고 보니

문제의 길이만큼 코드의 길이도 짧았다.

 

하지만 만약 코딩테스트나 시험에서 이 문제를 만났다면 쉽게 이분 탐색을 생각하지 못했을 것이다.

 

이 문제는 겉으로 보기에 배열을 만들어 정렬하면 될 것 같은 문제이지만,

입력의 크기가 최대 10^5 X 10^5으로 100억에 이르기 때문에 배열을 정렬하는 코드를 제출하면 "메모리 초과" 결과가 나온다.

 

먼저 이 문제를 보고 파라메트릭 서치가 떠오른다면 이렇게 생각할 수 있다.

배열에서 임의의 수 x에 대해서 x보다 작은 수의 갯수가 k보다 작다면 k는 그 갯수보다는 높은 번호를 가질 것이다.

x보다 작은 수의 갯수가 k보다 크다면 정답은 더 작은 숫자일 것이다.

 

위의 과정을 통해 이분 탐색을 생각해낼 수 있다.

물론 이 문제를 보고 이분 탐색까지 해결 방법을 생각해내는 것이 대단하고 많은 연습이 필요하다고 생각한다.

 

가장 먼저 해야할 일은 특정 숫자보다 작은 숫자들의 갯수를 구하는 일이다.

임의의 수 x를 던졌을 때 이 숫자보다 작은 숫자들이 N x N 배열에 몇 개나 있는지 알아야 한다.

 

이 문제의 배열은 이차원 배열로 i x j 형태로 나타낼 수 있으며,

특정 행의 특정 숫자보다 작거나 같은 숫자들의 갯수를 "x / 행 번호"로 나타낼 수 있다.

 

예를 들어,

문제에서 예제로 나온 n = 3, k = 7 입력을 보면

3 x 3 모양의 이차원 배열이 아래와 같이 존재할 것이다.

1	2	3
2	4	6
3	6	9

만약에 이 배열에서 7보다 작거나 같은 숫자들의 갯수를 구하고 싶다면,

1행) 7 / 1 = 7 [1, 2, 3] => 7 > n 이기 때문에 1행의 값은 n인 3이 들어간다.

2행) 7 / 2 = 3 [2, 4, 6]

3행) 7 / 3 = 2 [3, 6]

=> 8개

이렇게 구할 수 있다.

 

1행의 7 / 1 의 값은 n을 벗어나는 값들(1, 2, 3, 4, 5, 6, 7)을 모두 포함하는 값이기 때문에

n을 초과하는 경우 n 값을 넣어준다.

 

위의 규칙이 가능한 이유는 배열에 들어가는 값이 행과 열의 곱셈의 결과이기 때문이다.

x = i x j 이기 때문에 j = x / i 라는 식이 성립할 수 있다.

 

이제 어떠한 숫자가 들어와도 이 숫자가 몇 번째 숫자인지 알 수 있게 되었다.

우리가 구하고 싶은 것은 인덱스가 들어왔을 때 그 숫자가 무엇인지 맞추는 것이다.

 

따라서 1과 k 사이에서 이분 탐색을 진행하면 된다.

k까지 하는 이유는 행과 열의 곱셈으로 순서대로 이루어진 배열에서 k 번째 숫자가 k보다 클 수는 없기 때문이다.

 

1과 k 사이에서 중간값(mid)를 구하면서 mid 앞에 몇 개의 숫자가 있는지 반복해서 구한다.

k보다 그 합계가 작다면 start를 mid + 1로 옮기고

크다면 mid를 저장한 이후에 end를 mid - 1로 옮긴다.

 

start 와 end가 교차되는 순간 반복이 끝나면서 k 번째 숫자가 결과로 출력된다.

 

[소스 코드]

import sys

n = int(sys.stdin.readline().rstrip())
k = int(sys.stdin.readline().rstrip())

start = 1
end = k
result = 0

while start <= end:
    mid = (start + end) // 2
    count = 0
    for i in range(1, n + 1):
        count += min(int(mid / i), n)
    if count < k:
        start = mid + 1
    else:
        result = mid
        end = mid - 1

print(result)

기본적으로 주의해야 할 점이지만 파이썬에서 나눗셈을 할 때 특히 조심해야 하는 것 같다.

Python3에서는 특별히 형 변환을 하지 않아도 정수 / 정수를 실수형으로 자동으로 변환해서 저장한다.

그렇기 때문에 의도한 값이 아닌 다른 값이 나오는 경우도 있기 때문에 주의해야 한다.