[백준 알고리즘] 1026번 보물(정렬)

이번에 풀어볼 문제는 정렬을 활용한 문제로 백준의 1026번 보물 문제입니다.

문제는 여기

문제를 간단하게 보면 두 배열의 각 성분의 곱의 합(S = A[0]xB[0] + A[1]xB[1] + …)이 최소가 되도록 하는 거래네요.

풀이는 너무 간단하게..! 큰거에 작은거 곱해서 작게 만드는 것..!!! 간단..ㅎㅎ

저는 A를 오름, B를 내림차순 정렬해서 문제를 해결했습니다. 정렬 알고리즘은 퀵정렬을 사용해서 풀었습니다.

이건 제가 정리해본 정렬 알고리즘 글입니다..ㅎㅎ필력 제로..ㅠㅠ

---

제가 쓴 정렬 알고리즘ㅎㅎ - 선택,삽입정렬

제가 쓴 정렬 알고리즘ㅎㅎ -병합정렬

제가 쓴 정렬 알고리즘ㅎㅎ - 퀵정렬

---

코드는 다음과 같습니다!(C++사용했습니다.)

#include <iostream>
using namespace std;

void qsort_small(int* data, int left, int right)
{
    int l = left;
    int r = right;
    int pivot = data[left];
    while(l<r)
    {
        if((data[r] >= pivot)&& (l<r))r--;
        data[l] = data[r];
        if((data[l] < pivot)&&(l<r))l++;
        data[r] = data[l];
    }
    data[l] = pivot;
    if(left < l)
        qsort_small(data,left,l-1);
    if(l < right)
        qsort_small(data,r+1,right);
}
void qsort_big(int* data, int left, int right)
{
    int l = left;
    int r = right;
    int pivot = data[left];
    while(l<r)
    {
        if((data[r] < pivot)&& (l<r))r--;
        data[l] = data[r];
        if((data[l] >= pivot)&&(l<r))l++;
        data[r] = data[l];
    }
    data[l] = pivot;
    if(left < l)
        qsort_big(data,left,l-1);
    if(l < right)
        qsort_big(data,r+1,right);
}
int main()
{
    int N;
    int A[50],B[50];
    int result = 0;
    
    cin>>N;
    for(int i=0; i<N; i++)
        cin>>A[i];
    for(int i=0; i<N; i++)
        cin>>B[i];
    
    qsort_small(A,0,N-1);
    qsort_big(B,0,N-1);

    for(int i=0; i<5; i++) result += A[i]*B[i];
    cout<<endl<<result;
}

그럼 간단하게 마무리하겠습니다~!! ㅂㅂ~~~~