이진 탐색 문제 중, 조금 특이해 보여서 풀어보았다.
처음에 그냥 행렬만들고 정렬해서 하면 되겠지 하다가 골드 3인거 보고 아 안되겠구나 했다.
이거 문제를 어떻게 접근해야하나 고민하다가 답이 안나와서 좀 찾아봤는데, 조금 머리를 써야되는 풀이였다.
만약 이 배열 B에서 11번째, 즉 B[11]을 찾고 싶다고 가정하자.
B[11]의 숫자가 x라고 하면, 전체 숫자 중에서 x보다 작거나 같은 숫자의 수가 11보다 작으면 안된다.
만약 작다면, x가 더 커져야 한다.
이 (전체 숫자에서 x보다 작거나 같은 숫자의 수)를 가지고 이진 탐색을 한다.
그렇다면 이 (전체 숫자에서 x보다 작거나 같은 숫자의 수) 는 어떻게 구하느냐 하면, 각 행별로 계산을 접근해본다.
각 행은 i*1, i*2, i*3.... 의 모양이고, x를 i로 나눈 몫과 n 중 작은 것이 그 행에서 m 보다 작거나 같은 개수이다.
이 연산을 각 행마다 연산 후 더하면 전체 숫자 중 x보다 작거나 같은 숫자의 개수 이다.
이 값을 가지고 이진 탐색을 하면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
int n, k;
std::cin >> n >> k;
int start = 1;
int end = k; // b[k] 는 k보다 작거나 같음. => 이분 탐색의 종료점 = k;
int mid, ret = 0;
// b[11] 을 찾고 싶을때 -> b[11]의 숫자가 x라고 하면, 전체 숫자 중에서 x보다 작거나 같은 숫자의 수가 11보다 작으면 안됨.
// 만약 그렇다면, 찾는 숫자의 범위를 큰 쪽으로 옮겨야.
// 각 행에서 특정 숫자 m보다 작거나 같은 개수를 찾기
// 행 번호 i이면, min(m / i, N)
while (start <= end)
{
mid = (start + end) / 2;
int count = 0;
for (int i = 1; i <= n; i++)
{
count += std::min(n, mid / i);
}
if (count >= k)
{
ret = mid;
end = mid - 1;
}
else
start = mid + 1;
}
std::cout << ret;
}
코드를 더 뜯어보고 고민을 좀 해봐야겠다. 코드가 아주 간소하긴 한데 좀 이 배열에서 숫자를 세는 매커니즘과 이진 탐색으로 어떻게 값을 도출해 내는지에 대해 더 이해가 필요한 것 같다.
오늘도 평온한 하루가 되길. 슨민.
'짜잘한 기록' 카테고리의 다른 글
백준 1107 리모컨 (0) | 2021.11.25 |
---|---|
백준 1759 암호 만들기 (0) | 2021.11.23 |
백준 1981 배열에서 이동 (0) | 2021.11.18 |
백준 2470 두 용액 (0) | 2021.11.17 |
백준 1112 진법 변환 (0) | 2021.11.11 |