이분탐색 관련 문제들을 풀다가, 흥미로웠던 문제가 있어서 정리해보려 한다.
K번째 수라는 문제인데, 다음과 같이 생겼다.
문제는 상당히 짧고 간결한데, 어떻게 접근해야 할지 생각하느라 시간을 오래 사용했다.
처음에는 행렬이 대각선을 기준으로 대칭을 이룬다는 성질을 활용하려 했다. 1의 제곱, 2의 제곱 등 대각선에 위치한 N개의 숫자 외에는 2개씩 중복된 숫자들이 존재할테니, 그걸 고려해서 B[k]를 구할 때 k//2 + N 개 이내로만 체크해서 구할 수 있지 않을까하는 생각이었다. 하지만 이러한 접근 방식에는 문제가 있는데, 특정 숫자가 3번 이상 반복될 가능성이 존재하기 때문이다. 가령 N이 16이라면, 숫자 16은 1x16, 2x8, 4x4, 8x2, 16x1 이렇게 5번이나 나오게 된다.
또한 / 방향으로 대각선을 그려가며 숫자를 체크해가는 방법도 생각해보았다. 처음엔 1x1, 다음엔 1x2와 2x1, 다음엔 1x3, 2x2, 3x1... 이런 식으로 체크해가는 것이다. 하지만 이 역시 같은 이유로 문제가 있었다. N이 4 이상이면 2x2와 1x4, 4x1는 모두 4지만, 서로 다른 대각선에 존재하기 때문에 이렇게 세는건 의미가 없었다.
결과적으로 성공한 방법은 이분탐색으로 어떠한 특정 숫자를 기준으로 N개의 행을 모두 체크해가며, 그 특정 숫자보다 작거나 같은 숫자들의 갯수를 세어 확인하는 것이었다. 특정 숫자를 해당 행의 번호로 나눈 몫을 구했을 때 그 몫이 N보다 크거나 같다면, 해당 행의 모든 N개의 숫자는 특정 숫자보다 작거나 같다. 반면 위에서 구한 몫이 N보다 작다면, 그 몫만큼만이 특정 숫자보다 작거나 같다. 이러한 방법으로 N개의 행을 확인하면 O(N)의 시간복잡도로 특정 숫자가 마지막으로 몇 번째 인덱스에 해당하는지를 알 수 있다.
# BOJ # 1300 # K번째 수
import sys
input = sys.stdin.readline
N = int(input())
k = int(input())
def get_less_cnt(target):
cnt = 0
for i in range(1, N+1):
cnt += min(target // i, N) # i번째 행에서 몇 개의 숫자가 target 이하인지를 체크하고 cnt에 반영
return cnt
start = 1
end = N ** 2
while start <= end:
mid = (start + end) // 2
nowCnt = get_less_cnt(mid)
if nowCnt < k:
start = mid + 1
else:
end = mid - 1
print(start)만약 특정 숫자보다 작거나 같은 숫자들의 갯수가 딱 K라고 하더라도, 더 작은 숫자에서도 작거나 같은 숫자들의 갯수가 K일수도 있으니 탐색을 멈추지 않고 추가적으로 반복문을 수행해야 한다. 가령 N이 6 이하인 경우를 가정한다면, 숫자 7은 그 어떤 경우에도 만들 수 없다. 따라서 7보다 작거나 같은 숫자의 갯수는 6보다 작거나 같은 숫자의 갯수와 같다.
end가 아니라 start를 출력해주는 이유는 start == end인 경우를 생각해보면 된다. nowCnt가 k보다 작으면 현재 숫자 mid보다 1이 큰 숫자가 최종적으로 답이 되어야 한다. 또한 nowCnt가 k보다 크거나 같다면 현재 mid 값이 최종적으로 답이 되어야 한다. 따라서 start를 출력해주어야 정상적으로 값이 나오게 된다.
막상 해결하고 나니 풀이가 짧은데 생각은 정말 많이하게 되는 문제가 이분탐색인 것 같다. 어떤 숫자에 대해 이분탐색을 수행할지 정하고, start와 end를 알맞게 초기화해주는 것이 핵심인데 아직 좀 더 연습이 필요하다 🤣
