[ 백준 1026 ] 보물 (C++)

백준의 보물(1026) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 두 개의 배열에서, A배열만 재배치를 해서 주어진 식의 최솟값을 찾는 문제이다.

   그럼 직관적으로 생각을 해 봤을 때, A배열과 B배열의 동일한 Index값끼리 곱해서 더한 값이 최소가 되어야 하기 때문에

   곱한 값이 최소가 되어버리면 당연히 더한 결과도 최솟값이 될 것이다.

   그럼 곱해서 최소가 되려면 어떡해야할까 ?? 무조건 큰 값과 작은 값이 만나도록 만들어 주어야 한다.

   큰 값과 큰 값이 만나면 당연히 그 결과값이 커질 것이고 , 큰 값과 작은 값이 만나면 그 값은 더 작아질 것이다.

   즉, A배열을 오름차순으로, B배열을 내림차순으로 정렬 후 곱해서 더해버리면 된다.

   그런데 B배열은 재배열 하면 안된다고 했는데 ??

   우리는 결과값을 구하기 위해서 이렇게 정렬을 했을 뿐, B를 재배치 하지는 않았다고 볼 수 있다.

   예제입력 1을 봐보자.

   [ 1 , 1 , 1 , 6 , 0 ] , [ 2 , 7 , 8 , 3 , 1 ] 이 있을 때 이를 위와 같이 정렬 시켜보면

   [ 0 , 1 , 1 , 1 , 6 ] , [ 8 , 7 , 3 , 2 , 1 ] 이 될 것이고 곱해서 더하면 18이 나오게 된다.

   근데 B를 재배치 시켰잖아 ???

   다르게 보면 다음과 같이 볼 수 있다.

   B를 재배치 시키지 않고 [ 2 , 7 , 8 , 3 , 1 ] 로 두고, A배열을 [ 1 , 1 , 0 , 1 , 6 ] 으로 배치시켰다고 볼 수 있다.

   즉, B를 재배치 시키면 안된다는 말이 있었지만 사실 정답을 출력하는데에는 아무런 지장이 없다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N;
int Arr_A[MAX];
int Arr_B[MAX];
bool Select[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Arr_A[i];
    for (int i = 0; i < N; i++) cin >> Arr_B[i];
}
 
bool Cmp(int A, int B)
{
    if (A > B) return true;
    return false;
}
 
void Solution()
{
    sort(Arr_A, Arr_A + N);
    sort(Arr_B, Arr_B + N, Cmp);
    int Sum = 0;
    for (int i = 0; i < N; i++) Sum = Sum + (Arr_A[i] * Arr_B[i]);
    
    cout << Sum << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}