[AtCoder - ARC037 C] 億マス計算

난이도: 1824 // Experimental

 

번역

C. 1억 번이 넘는 계산

 

Takahashi는 \( N^2 \)회의 많은 계산이라는 방식으로 본인의 계산 능력을 늘리려 합니다.

\( N^2 \)회의 많은 계산은 아래와 같이 진행됩니다.

 

우선, \( N \times N \) 크기의 행렬을 준비합니다.

그리고, 행렬의 맨 왼쪽 줄의 왼쪽에는 \( A_{i} \)를 차례로 적고, 맨 윗줄의 위에는 \( B_{j} \)를 차례대로 적습니다.

이제, \( (i, j) \)의 위치에 있는 칸에는 \( A_{i} \times B_{j} \)를 적습니다.

 

Takahashi는 이를 너무 간단하게 끝냈기 때문에, 이렇게 적은 \( N^2 \)개의 수를 정렬해보기로 했습니다.

이 때, 정렬 후 앞에서부터 \( K \)번째에 위치하게 되는 원소를 출력하세요.

즉, \( N^2 \)개의 수 중 \( K \)번째로 작은 원소의 값을 출력하세요.

 

태그

• Binary Search
• Parametric Search
• Sort

 

풀이

0. 시작하기 전: 간단한 조작

배열 \( A \)와 \( B \)가 정렬되어있어도 답에 영향을 끼치지 않으니, 풀이에서는 \( A \)와 \( B \)가 정렬되어있다고 가정합니다.

 

1. \( K \)번째로 작은 원소는 어떻게 찾을 수 있을까?

어떤 수 \( X \)를 생각해봅시다.

만약 배열에 쓰인 수 중 \( X \) 이하인 수의 개수가 \( K \)개 이상이라면, 문제의 답은 \( X \) 이하가 됩니다.

반대로, \( K \)개 미만이었다면 문제의 답은 \( X \) 초과가 되겠죠.

 

이는, 문제의 답을 이진 탐색으로 찾을 수 있음을 의미합니다.

 

그런데, \( X \) 이하인 수의 개수는 어떻게 찾을까요?

 

2. 어떤 하나의 가로줄에 대해, \( X \) 이하인 수의 개수는?

가로줄을 하나로 고정시켰습니다.

그 가로줄에 있는 모든 수들은 \( A_{i} \times b \)의 형태로 이루어져있겠죠.

 

하지만 \( A_{i} \)를 모두 곱해두고 있는 건 뭔가뭔가 하니, 대신에 \( b \)만 남겨둡시다.

그럼, 우리가 세야 하는 수의 개수는 \( \frac{X}{A_{i}} \) 이하인 수의 개수가 됩니다.

 

이 역시 이진 탐색으로 찾을 수 있으며, 이 과정을 \( N \)개의 가로줄에 대해 각각 해주면 됩니다.

 

3. 정리

그러니까...

값을 이진 탐색하는 과정에서 (\( O(\log X) \))

하나의 가로줄을 볼 때마다 (\( O(N) \))

또 이진 탐색을 돌려야 합니다. (\( O(\log N) \))

 

다 곱하면 대략 2700만 정도의 값이 나오는 수치죠.

 

4. 코드

옛날 AtCoder 문제는 출력 끝에 개행을 해줘야 함에 주의하세요.

ll arr[30020], brr[30020];
 
void Main(){
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; } sort(arr+1, arr+n+1);
    for (int i = 1; i <= n; i++){ cin >> brr[i]; } sort(brr+1, brr+n+1);
    ll st = 1, ed = 1e18, ans = 1e18; while (st <= ed){
        ll mid = st+ed >> 1; ll cnt = 0;
        for (int i = 1; i <= n; i++){
            ll val = mid/arr[i];
            auto idx = upper_bound(brr+1, brr+n+1, val) - (brr+1);
            cnt += idx;
        }
        if (cnt >= k){ ed = mid-1; ans = mid; } else{ st = mid+1; }
    }
    cout << ans << endl;
}