BOJ 1026 - 보물 문제풀이

문제를 읽고 이해하기

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] * B[0] + ... + A[N-1] * B[N-1]

 

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

 

재정의와 추상화

정렬 문제

 

문제에서 A만 재배열하여 A[0] * B[0]부터 A[N-1] * B[N-1]까지 더한 값의 최소값을 출력하라고 했다. 이 값이 최소가 되려면 A의 최대값은 B의 최소값과 곱해져야 하고, A의 최소값은 B의 최대값과 곱해져야 한다. 즉, A는 오름차순, B는 내림차순으로 정렬된 상태에서 처음부터 인덱스 끝까지 곱한 것을 더하면 된다는 의미이다.

 

따라서 알고리즘은

1. 배열 A와 B를 입력받는다.
2. A를 오름차순, B를 내림차순으로 정렬한다. (그 반대도 똑같다.)
3. A와 B를 0부터 n-1까지 서로 곱한 것을 더한다.
4. 그 값을 출력한다.

이다.

 

코드 작성

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

bool comp(int a, int b) {
    return a > b;
}

int main() {
    int n, sum = 0;
    vector<int> a, b;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        a.push_back(temp);
    }

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        b.push_back(temp);
    }

    sort(a.begin(), a.end(), comp);
    sort(b.begin(), b.end());

    for (int i = 0; i < n; i ++)
        sum += a[i] * b[i];

    cout << sum;

    return 0;
}