백준(1300번, K번째 수, 골드I)

문제 내용

문제 내용

---

제출한 코드

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());
        int K = Integer.parseInt(br.readLine());

        long start = 1;
        long end = K;
        long answer = 0;

        while (start < end) {
            long mid = (start + end) / 2;
            long count = 0;

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

            if (count < K) {
                
                start = mid + 1;
            } else {
                
                end = mid;
            }
        }

        System.out.println(start);
    }
}

---

풀이과정

수도코드는 아래와 같이 작성했고

1. 시작점(start) = 1, 끝점(end) = K(K번째 수는 최대 K보다 클 수 없기 때문)
2. 중간 값(mid)을 설정하고, 배열 A에서 mid 이하의 수가 몇 개 계산해줌
3. mid 이하의 수가 K개 이상이면 → mid는 정답 후보일 수 있으니 end를 줄인다
4. mid 이하의 수가 K보다 적다면 → mid는 너무 작으므로 start를 올린다
5. start와 end가 같아지면, 그 수가 정확히 K번째 수

 

접근법은 나쁘지않았는데, N의 최대값이 100,000으로 너무너무 커서
직접 배열 만들기보다는 각 행에서 mid보다 작은 수 몇 개인지 구하면 되지 않을까라는 binary search를 써야된다는 접근을 했다

막혔던 부분은 각 행에서 mid보다 작은 수가 몇 개인지를 규칙을 찾는게 어려웠어서, 구글링을 하며 다른 사람들의 풀이를 참고하기 시작했다

i행은 i × 1, i × 2, ..., i × N 으로 구성됨  
→ 즉, i행에서 mid보다 작거나 같은 수는 mid / i 개  
→ 단, 최대 N개까지만 존재하므로 min(mid / i, N) 으로 처리

위 내용은 내가 구글링을 하며 정리해본 내용인데, 이해가 잘되지 않는다면 아래의 설명들을 참고해주면 좋을거같다

 

이분탐색 범위

이분 탐색 Lower-Bound

해당 문제를 풀이하면서 고민 했던 점은 크게 아래 두가지 였다

이분탐색에서 정답이 아닐 때는 +1이나 -1 를 해줬어서 mid가 K번째 수가 아닐 수도 있는데 왜 count >= k일 때 end = mid로 줄이는 건지 ?

➡️ count >= k 자체가 mid가 K번째 수일 수도 있고, 혹은 K번째 수보다 큰 수일 수도 있다는 뜻이라서 정답 후보로서 가능성이 있으니까 버리면 안됨

 

count == k일 때 정답을 찾은 거니까 바로 mid를 출력하면 안되나 ?

➡️ count == k 라고 해서 그게 반드시 딱 K번째 수라는 뜻이 아니고, mid보다 더 작은 수 중에서도 K번째 수가 존재할 수 있음

---

후기

추가적으로 이분 탐색에서 조건을 만족하는 수 중에, 가장 작은 값을 찾아야 되는 경우에는 end = mid로 유지해야 한다는 것도 알게되었고, 이후 문제부터는 이분탐색이 절반씩 나눈다 라기보다는 정답 후보는 점점 남기고 아닌걸 더 줄여나가자라는 개념으로 접근해야겠다고 생각했다

개인적으로 지금까지 푼거중에 젤 어려운 편이였었고, 내 힘으로만 풀이한 느낌이 아니여서 해당 문제는 나중에 꼭 다시 한번 풀어봐야할거같다 😂

 

참고한 자료

https://st-lab.tistory.com/281