[BOJ 1026 // C++] 보물

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1026번 문제인 보물이다.
문제는 아래 링크를 확인하자.
www.acmicpc.net/problem/1026

1026번: 보물

네 수의 a1<a2, b1<b2가 있을 때, a1*b2+a2*b1<a1*b1+a2*b2이 항상 성립하므로, 이 문제는 주어진 A와 B를 정렬한 뒤 역순으로 서로 곱한 합을 구하는 것으로 풀 수 있다.

 

문제에서 B의 순서를 건드리지 말라고 했으나, B의 순서를 건드려도 안 건드려도 출력해야하는 값은 같으므로 B의 순서를 바꿔도 상관이 없다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int main()
{
    int arrA[50], arrB[50]; //A와 B를 받아 정렬하기
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        arrA[i] = x;
    }
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        arrB[i] = x;
    }
    sort(arrA, arrA + n);
    sort(arrB, arrB + n);
    int ans = 0;
    for (int i = 0;i < n;i++) { // 큰 수와 작은 수를 순서대로 곱해 더한다
        ans += arrA[i] * arrB[n-1-i]; 
    }
    cout << ans;
}