[백준/Java] 1300 : K번째 수

📌 문제 정보

• 번호: 1300
• 제목: K번째 수
• 난이도: Gold 1
• 분류: 이분 탐색

---

💡 접근 방식

"mid 이하인 값이 배열에 몇 개 있는가?"를 O(N)으로 계산할 수 있다면, 이분탐색으로 K번째 값을 찾을 수 있음
배열을 실제로 만들지 않고, 조건 함수만으로 정답을 좁혀나가는 Parametric Search 방식

---

🔹 단계별 풀이

1단계 – i행에서 mid 이하인 값 개수 계산

i행은 i, 2i, 3i, ..., Ni (i의 배수들)로 구성
이 중 mid 이하인 값의 개수 = j × i ≤ mid를 만족하는 j의 수 = mid / i (정수 나눗셈)

단, 행에는 값이 N개만 존재하므로 N을 초과할 수 없음

N=3, mid=7 기준:
1행: min(7/1, 3) = 3
2행: min(7/2, 3) = 3
3행: min(7/3, 3) = 2
합계 count = 8

for (int i = 1; i <= N; i++) {
    count += Math.min(mid / i, N);
}

2단계 – 이분탐색으로 최솟값 탐색

count >= k를 만족하는 가장 작은 mid 를 찾는 것이 목표

• count < k → mid가 너무 작음 → left = mid + 1
• count >= k → 정답 후보 저장 후 더 작은 값 탐색 → answer = mid, right = mid - 1

N=3, k=7 탐색 예시:
mid=4 → count=6 < 7  → left=5
mid=7 → count=8 ≥ 7  → answer=7, right=6
mid=5 → count=7 ≥ 7  → answer=5, right=4
종료 → 최종 answer=5

탐색 범위: left=1, right=k (K번째 수는 최대 k)

---

💻 핵심 코드

while (left <= right) {
    long mid = (left + right) / 2;
    long count = 0;
    for (int i = 1; i <= N; i++) {
        count += Math.min(mid / i, N);
    }

    if (count < k) {
        left = mid + 1;
    } else {
        answer = mid;
        right = mid - 1;
    }
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N log K)
  • 이분탐색 O(log K) × 각 단계에서 count 계산 O(N)
• 공간 복잡도: O(1)
  • 배열 없이 변수만 사용

---

📄 전체 코드

package rtaeho.week02.B1300;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        long k = Long.parseLong(br.readLine());

        long left = 1;
        long right = k;
        long answer = 0;

        while (left <= right) {
            long mid = (left + right) / 2;
            long count = 0;
            for (int i = 1; i <= N; i++) {
                count += Math.min(mid / i, N);
            }

            if (count < k) {
                left = mid + 1;
            } else {
                answer = mid;
                right = mid - 1;
            }
        }

        System.out.print(answer);
    }
}