[BOJ / C++] 보물 (그리디)

문제링크: https://www.acmicpc.net/problem/1026

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), [](int a, int b) {return a > b;});

    int s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i] * b[i];
    }
    cout << s;
}

 

 

2. 분석

가장 큰 것과 가장 작은 것을 곱해서 더하면 최소가 되고, 가장 큰 것과 가장 큰 것을 곱해서 더하면 최대가 된다. 따라서 하나는 오름차순으로 하나는 내림차순으로 정렬해서 곱해서 더하면 끝난다.

 

3. 시간복잡도

정렬에 시간복잡도가 가장 크게 걸린다. O(nlgn)이고 n = 50 이므로 nlgn = 300 < 10^8 이므로 시간제한 2초 내에 통과 가능하다.