[백준][1026번][C++] 보물

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

1026번: 보물

길이가 같은 정수배열 A와 B의 인덱스가 같은 항끼리의 곱의 합이 최소가 되게 만드는 문제이다.

 

나름 문제를 어렵게 만들기위해 배열 B에 있는 수를 재배열하면 안된다고 문제에 명시해두었다.

 

하지만 배열 A를 마음껏 재배열 할 수 있으므로 사실 B의 순서는 아무런 의미가 없다.

 

N이 4라고 가정하면

S = A[0]*B[0] +  A[1]*B[1] +  A[2]*B[2] +   A[3]*B[3]

일 때 A배열의 원소들을 마음껏 재배열 할 수 있으므로

S = A[0]*B[0] +  A[3]*B[1] +  A[2]*B[2] +   A[1]*B[3]

또한 가능할 것이다.

이 때 항의 순서를 재배열하면

S = A[0]*B[0] +  A[1]*B[3] +  A[2]*B[2] +  A[3]*B[1]

이므로 A배열의 원소들을 재배치 할 수 있다는 것은 B배열의 원소들 또한 재배치 할 수 있다는 것을 의미한다는 것을 알 수 있다.

 

S를 최소로 만드려면 배열 A와 B를 각각 오름차순, 내림차순으로 정렬해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

int main()
{
    int N, num, ret=0;
    vector<int> a, b;
    
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&num);
        a.push_back(num);
    }
    sort(a.begin(),a.end());
    for(int i=0;i<N;i++)
    {
        scanf("%d",&num);
        b.push_back(num);
    }
    sort(b.begin(),b.end(),greater<int>());
    
    for(int i=0;i<N;i++)
    {
        ret+=a[i]*b[i];
    }
    printf("%d",ret);
    
    return 0;
}