k의 범위가 1 ~ 이므로 시간복잡도가 인 알고리즘은 사용할 수 없다.
이 말은 N x N과 같은 2차원 배열에서 직접 원소를 모두 확인하는 방법이 불가능하다는 의미이다.
그래서 이 문제 역시 이진 탐색을 사용해야 하는데, 사실 이진 탐색 알고리즘을 사용해야한다는 것 자체를 떠올리기가 쉽지 않다...
먼저 문제 이해를 위해 예제 입력을 그림으로 표현하면 다음과 같다.
3 x 3 배열인 A에서 7번째로 작은 수인 6을 출력하면 되는 것이다.
여기서 핵심은 각 행의 숫자들은 모두 각 행의 첫번째 원소의 배수라는 점이다.
문제에서 A[i][j] = i x j 라고 정의하였기 때문에, 3 x 3 배열은 마치 1 ~ 3단까지 적힌 구구단처럼 나열되어 있다는 의미이다.
첫 번째 행: 1, 2, 3
두 번째 행: 2, 4, 6
세 번째 행: 3, 6, 9
이 말은 즉 mid // i (i = 1, 2, 3... N)한 결과는 각 i번째 행에서 k보다 작은 숫자의 개수이다.
이해를 위해 아래 그림을 보자.
우리가 찾고자 하는 k번째 수는 1 ~ k 안에 있으므로 start = 1, end = k로 둔다.
그 후 mid = (start + end) // 2를 계산하여 중앙값을 구한다.
이제 위에서 설명한 mid // i 계산을 N번 반복하며 k보다 작은 숫자의 개수를 구하는 것이다.
예제 입력에 따른 그림의 풀이 순서는 아래와 같다.
-
mid = (1 + 7) / 2 = 4인데, N = 3 이므로4 / 1 = 4,4 / 2 = 2,4 / 3 = 1를 구하여 모두 더한다.
※ 단, 나눈 값이 N보다 큰 경우 N의 값으로 조정함따라서
3 + 2 + 1 = 6이 되고, 이는 k = 7인 수보다 작은 숫자의 개수가 6개이며, mid 보다 작은 숫자가 충분하지 않아 더 큰 수를 찾아야 한다는 의미이다.그러므로
start = mid + 1 = 5를 계산하여 더 큰 범위로 이동한다. -
새롭게 업데이트 된 start를 넣어서 다시 mid 값을 계산하면 다음과 같다.
mid = (5 + 7) / 2 = 6, N = 3 이므로6 / 1 = 6,6 / 2 = 3,6 / 3 = 2를 구하여 모두 더한다.
※ 단, 나눈 값이 N보다 큰 경우 N의 값으로 조정함따라서
3 + 3 + 2 = 8이 되고, 이는 k = 7인 수보다 작은 숫자의 개수가 8개이며, mid 보다 작은 숫자가 충분하므로 일단 answer에 mid값을 잠정적인 정답으로 저장한다.그리고
end = mid - 1 = 5를 계산하여 더 작은 범위로 이동한다. -
새롭게 업데이트 된 end를 넣어서 다시 mid 값을 계산하면 다음과 같다.
mid = (5 + 5) / 2 = 5, N = 3 이므로5 / 1 = 5,5 / 2 = 2,5 / 3 = 1를 구하여 모두 더한다.
※ 단, 나눈 값이 N보다 큰 경우 N의 값으로 조정함따라서
3 + 2 + 1 = 6이 되고, 이는 k = 7인 수보다 작은 숫자의 개수가 6개이며, mid 보다 작은 숫자가 충분하지 않아 더 큰 수를 찾아야 한다는 의미이다.그러므로
start = mid + 1 = 5를 계산한다.
근데 3번 마지막에서 start > end = 6 > 5이므로 반복문 탈출조건이 성립되어 나가게 되고, 정답은 이전에 2번에서 저장했던 answer = 6이다.
Python
따라서 파이썬의 전체 소스코드는 다음과 같다.
import sys
input = sys.stdin.readline
N = int(input())
k = int(input())
start = 1
end = k
answer = 0
while start <= end:
mid = (start + end) // 2
total_count = 0
for i in range(1, N + 1):
# 각 행에서 k보다 작은 숫자의 개수 구하기
row_count = mid // i
# 주어진 N의 범위보다 넘는 경우는 N으로 조정
if row_count >= N:
row_count = N
# 각 행에 대해 k보다 작은 수를 모두 더하기
total_count += row_count
# mid보다 작은 숫자가 충분하지 않는경우
if total_count < k:
start = mid + 1
# 우리가 찾는 숫자가 mid 이하에 있으므로
else:
end = mid - 1
answer = mid
print(answer)Java
따라서 자바의 전체 소스코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.Math;
public class P_1300 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
int start = 1;
int end = k;
int answer = 0;
while (start <= end) {
int mid = (start + end) / 2;
int count = 0;
for (int i = 1; i <= N; i++) {
count += Math.min(mid / i, N);
}
if (count < k)
start = mid + 1;
else {
answer = mid;
end = mid - 1;
}
}
System.out.println(answer);
}
}왜 min(mid // i, N)이 각 행에서 k보다 작은 숫자의 개수인지 궁금할 수 있다.
각 행 i의 원소는 i의 배수라는 점을 생각해보자.
i, 2i, 3i, ..., Ni 순서로 i 간격으로 일정하게 증가하므로, 각 행에서 k보다 작은 숫자의 개수는 min(mid // i, N)이고, min(mid // i, N)은 k보다 작은 숫자의 개수가 총 몇 개인지 카운트할 수 있다.
