[백준] 1300번. K번째 수(JAVA)
문제
https://www.acmicpc.net/problem/1300
풀이(1시간29분)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); // n x n 크기의 곱셈표
int k = Integer.parseInt(br.readLine()); // k번째로 작은 수를 찾기
long left = 1;
long right = k;
// 이진 탐색으로 k번째 수를 찾는다 (lower bound)
while (left < right) {
long mid = (left + right) / 2;
long count = 0;
// 곱셈표의 각 행에서 mid 이하인 수의 개수를 누적
for (int i = 1; i <= n; i++) {
// i행에서 mid 이하인 수의 개수는 mid / i,
// 단, 한 행의 최대 열 개수는 n
count += Math.min(mid / i, n);
}
// count가 k 이상이면 mid는 k번째 수 이상일 수 있음 → 더 작은 수 가능
if (count >= k) {
right = mid;
} else {
left = mid + 1;
}
}
// left는 k번째로 작은 수
System.out.println(left);
}
}문제 풀이 전략
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 2 | 3 | 4 |
| 2 | 2 | 4 | 6 | 8 |
| 3 | 3 | 6 | 9 | 12 |
| 4 | 4 | 8 | 12 | 16 |
이 표를 그려놓고 문제를 풀었다.
💡 약수를 이용하면 되지 않을까?
첫 번째 아이디어는 약수를 이용하는 것이었다.
예를 들어 생각해 보자.
이러한 공식을 기억하는가? 중고등학교 시절에 약수의 개수를 구하기 위해 매우 많이 사용했던 공식이다.
이를 위해서는 소인수분해를 거쳐야 했고, n = 10^5까지 가능한 문제 특성상 너무나도 많은 연산을 요구하기에 포기했다.
하지만, 얻은 점이 있었다.
분명한 건 어떻게든 약수에 관한 공식을 찾아야 한다는 것과, 약수를 통해 계산하다 보면 초과하는 부분(아래 설명하겠다.)이 필연적으로 발생하는데 이 경우 최대 N으로 제한을 걸면 되겠구나!라는 것이다.
💡 분명 약수를 이용해야 한다.
약수에 집착했던 이유는 너무나도 큰 문제 조건을 보았을 때 이분탐색을 이용할 것이라는 게 본능적으로 느껴졌기 때문이다. 그렇다면 나열은 아닐 것이고... 어떤 식으로든 근거가 있다는 뜻이다.
그렇기에 생각해 낸 것이 B[k] = x 라는 것인데 여기서 x이하의 개수는 몇 개인지 알 수 있는 방법이 없을까?라는 생각을 했다.
최종적으로 도출해 낸 아이디어는 다음과 같다.
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 2 | 3 | 4 |
| 2 | 2 | 4 | 6 | 8 |
| 3 | 3 | 6 | 9 | 12 |
| 4 | 4 | 8 | 12 | 16 |
이 표를 다시 돌이켜보며 9 이하는 몇 개의 숫자가 있는지 생각해 보자.
1단에서 4개, 2단에서 4개, 3단에서 3개, 4단에서 2개가 있다.
느낌이 오는가?
1단의 경우 -> 9/1 = 9 -> 즉, 9 이하의 숫자가 9개 있을 수 있다.
2단의 경우 -> 9/2 = 4.5 -> 즉, 9 이하의 숫자가 4개 있을 수 있다.
3단의 경우 -> 9/3 = 3 -> 즉, 9 이하의 숫자가 3개 있을 수 있다.
4단의 경우 -> 9/4 = 2.25 -> 즉, 9 이하의 숫자가 2개 있을 수 있다.
나눗셈을 생각하면 꽤나 당연한 이야기이다.
그렇다면 위에 초과하는 부분(1단의 경우 9개)을 모두 세면 안 된다. 왜냐하면 N = 4로 제한이 걸려있기 때문이다. 그렇기에
count += Math.min(mid / i, n);연산이 필요하다. 만약 n을 넘는다면 최대 n개만 사용하겠다는 의미이다.
최종적으로 이를 이분탐색으로 찾아주면 된다!
여기서 right = k를 사용하는 이유는 n*n을 써도 되지만 k를 조정하다 보면 어차피 정답은 k이하겠구나라는 것을 알게 됐기에 사용하였다.