[C++][백준 12991] 홍준이의 행렬

[문제]

https://www.acmicpc.net/problem/12991

12991번: 홍준이의 행렬

---

[문제 풀이]

k번째 수 와 비슷한 문제이다.

다만, k번째 수는 1부터 n까지 순서대로 가기 때문에 우리가 어떤 숫자가 올지 예측이 되었지만 여기선 입력을 받은 숫자이기 때문에 예측이 되지 않는다는 문제가 있다.

해당 부분을 해결하기 위해서 이분 탐색을 한번 더 쓰는 방식으로 해결을 하였다.

 

k번째 수에서 이미 배웠지만 다시 한번 복습을 해가도록 하자.

예시를 통해서 문제를 살펴보도록 하자.

첫번째 벡터가 {1,3,4,5,6,8,9} 인 벡터이며

두번째 벡터가 {2,3,4,5,7,8,9} 인 벡터가 있다고 가정하자.

이와 같은 표가 있다면 해당 표 내에서 가장 작은 값은 2가 될 테고 가장 큰 값은 81이 될것이다.

그렇다면 우리들은 2와 81 사이에 k번째 수가 있다는 사실을 알 수가 있으니 이분 탐색을 통해서 언제 k번째 수가 되는지를 파악해 보도록 하자.

임의의 수 45라는 숫자를 예시로 들어보도록 하자.

45이하의 숫자를 표에서 세어봤을 때 7,7,7,7,5,4,4가 나오니 총 41개가 되어서 해당 벡터들에서 45는 41번째 숫자라는 것을 파악할 수가 있다.

이런 의문이 들 수도 있다. 46도 세어보면 41번째 숫자인데 그러면 45하고 겹치니 안되지 않나? 라는 의문이 생길 수 있다.

 

하지만, 우리들은 이분 탐색을 통해서 계속해서 탐색을 해 나갈 것이고 숫자 2부터 81까지를 계속해서 이분 탐색을 할 것이므로 46이 41번째라면 41번째 숫자인 45까지 탐색을 해 나갈 것이다.

즉, 이분 탐색을 통해서 숫자를 판별하고 해당 숫자를 표의 n번을 돌려보면서 이하의 숫자의 개수를 파악해서 모두 더해준다면 해당 숫자가 몇번째인지를 파악이 가능하다.

이를 통해서 k번째 숫자를 파악할 것이다.

 

여기까지가 k번째 수에서 배웠던 방식이다.

다만, k번째 수에서는 숫자가 정해져있었기에 더해야할 값이 몇인지를 수식으로 바로 나타낼 수가 있었는데 여기서는 그렇게 풀 수가 없는 상황이다.

 

이를 해결하기 위해서 한번 더 이분 탐색을 이용해보도록 하자!

이분 탐색을 이용해서 각 행에 도달할 시 해당 숫자 이하의 수가 몇개인지를 파악하는 함수를 하나 더 만들어 보도록 하자.

 

이와 같은 내용이면 7에서는 처음에 mid가 4아니 35일테고 45보다 35는 작으니 다음은 start를 mid+1로 이동시켜서 mid가 6이 될 것이다.

그렇다면 56가 될 것이고 56보다 45는 작으니 high를 mid - 1로 이동시켜서 mid는 5가 될 것이고 이를 통해서 42까지가 45보다 작다는 것을 파악할 수가 있다.

 

그러니 더해주는 값에5를 더해주고 이와 같은 방식을 행렬의 시작부터 n번 행렬까지 반복해주면 풀 수가 있다.

---

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,k;
vector<long long> first_vector(30001,0);
vector<long long> second_vector(30001,0);

long long binary_sum(long long mid, int i){ //i번째 행렬에서 mid보다 작은 숫자가 몇개가 있는지 파악하는 함수.

    long long answer = 0;
    long long start = 0;
    long long high = n;
    long long middle = 0;

    while(start<=high){
        middle = (start + high + 1) / 2;
        if(first_vector[middle] * second_vector[i] <= mid){ //second_vector[i]는 i번째 행렬에 곱해지는 값을 의미.
                                                            //first_vector[middle]을 통해서 위치 파악.
                                                            //행렬을 곱해서 나온 값이 만일 mid값보다 작거나 같다면
            answer = middle;
            start = middle + 1;
        }
        else{ // mid값보다 크다면
            high = middle - 1;
        }
    }
    return answer;
}

long long vector_sum(long long mid){
    long long answer = 0;
    for(int i = 1;i<=n;i++){ //1부터 n까지 각 행에 몇개를 더할 수 있는지 판별.
        answer += binary_sum(mid,i); //lower bound로 풀고 싶었지만 그러자니 행렬을 만들어야 하고 그러면 시간초과가 나서 따로 구현했음.
    }
    return answer;
}

int main() {
    cin>>n>>k;

    for(int i = 1;i<=n;i++){
        cin>>first_vector[i];
    }
    for(int i = 1;i<=n;i++){
        cin>>second_vector[i];
    }

    //이분 탐색을 쓰기 위해서 정렬을 해주자.
    sort(first_vector.begin() + 1,first_vector.begin() + n + 1);
    sort(second_vector.begin() + 1,second_vector.begin() + n + 1); 

    long long start = first_vector[1] * second_vector[1]; //시작은 제일 작은값으로 시작하자.
    long long high = first_vector[n] * second_vector[n]; //끝은 가장 높은 값.
    long long mid = 0; //mid 설정.
    long long answer = 0; //answer

    while(start<=high){ //이분 탐색 시작. 
        mid = (start + high) / 2; 
        if(vector_sum(mid) < k){ //두 벡터를 곱해서 나온 벡터에서 mid값 이하의 숫자가 k개 이하라면.
            start = mid+1; //start를 1 증가시켜주자.
        }
        else{ //아니라면
            answer = mid; //answer = mid
            high = mid - 1; //high 를 1 빼주자.
        }
    }
    cout<<answer<<endl; //닶 출력.

    return 0;
}

*sort에서 끝나는 범위를 n+1 까지 안해가지고 계속해서 틀렸었다... 범위에는 언제나 주의하도록 하자!