[백준] K번째 수

[hye-on]

🔗 K번째 수

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include using namespace std; long long n, k, ans; int main() { cin >> n >> k; long long start = 0, end = n * n + 1,mid=0; int t = 0; long long ans = 0; while (start+1< end) { //start n ? n : mid / i; if (t == 0) break; sum += t; } if (sum < k) { start = mid; } else { ans = mid; end = mid; } } cout << ans; } ```

코멘트

- 수학 식? 규칙을 찾으려고 해서 처음에 헤맸습니다.
- 이분탐색인 것을 알고 나서도 경계를 설정해주는게 어려웠네요. 맨날 헷갈리는 것 같아서 이거 봤는데 괜찮은 것 같습니당 [이분 탐색(Binary Search) 헷갈리지 않게 구현하기](https://www.acmicpc.net/blog/view/109)

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; /** * 15:30 시작! 17:51 끝! (2시간 20분..) */ public class Main { /** * 1 2 3 4 5 * 2 4 6 8 10 * 3 6 9 12 15 * 4 8 12 16 20 * 5 10 15 20 25 * * O(N^2) ~= 10_000_000_000 시간 초과! 애초에 다 채우는 것을 할 수 없음! * 부분적으로 정렬이 되어있다는 것이 핵심! (정렬? 이분탐색?) * Sol. 1 ~ n^2을 이분 탐색해서 정답(x)을 구하자. * K번째 수란, x 보다 작거나 같은 수가 최소 K개 있다는 의미이다. */ public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(bf.readLine()); int k = Integer.parseInt(bf.readLine()); long left = 1; long right = k; // right를 n^2으로 잡지 않아도 됨. B[k] = x일 때, x는 k보다 작거나 같다. while(left <= right) { long mid = left + (right - left) / 2; long countLessOrSame = 0; // mid보다 작거나 같은 수의 갯수 int countOfSame = 0; for(int row = 1; row <= n; ++row) { countLessOrSame += Math.min(mid / row, n); if(mid % row == 0 && mid / row <= n) countOfSame++; } if(countLessOrSame < k) { left = mid + 1; } else if(countLessOrSame - countOfSame >= k) { right = mid - 1; } else { System.out.println(mid); break; } } } } ```

코멘트

- 행/열 별로 정렬이 되어 있다는 점에서 이분탐색을 생각했습니다! 큰 아이디어는 이분탐색으로 정답 후보를 찾고, 이 후보보다 작거나 같은 숫자가 k개 이상 있는지 확인하면 되는 문제였습니다.
- 저는 어떤 임의의 수 x에 대해서 x보다 작거나 같은 수의 갯수를 구할 때, 또 이분탐색을 써서 이분탐색 중첩으로 풀이를 했었는데, 정답을 참고해보니 수학적으로 계산이 가능하더라구요🤣 이 부분을 떠올리기 힘들어서 골드 1인 것 같습니다..