[C++] 백준 온라인 저지 1026번 보물 풀이

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

위와 같이 정의된 함수 S가 주어진다. 

A와 B 배열이 주어질 때 S의 최솟값을 구하는 문제

 

---

문제의 조건

 

1. 두 배열의 길이 N이 주어진다. 

 

2. N은 50보다 작거나 같은 자연수이고 

A, B의 각 원소는 0보다 크거나 같고 100보다 작거나 같은 양의 정수이다. 

 

3. B는 정렬하면 안 되고 A만 정렬해서 S의 최솟값을 구해서 출력하기 

 

---

풀이 과정

 

처음 문제를 읽었을 땐 A 배열을 정렬해서 풀어야 할 것 같지만 

예제를 자세히 보면 정렬할 필요가 없다는 것을 알 수 있습니다. 

 

A의 첫번째 최솟값과 B의 첫번째 최댓값을 곱한 값에다

A의 두번째 최솟값과 B의 두번째 최대값을 곱해서 첫번째로 구한 값에 더해주고

A의 세번째 최솟값과 B의 세번째 최댓값을 구해서 곱한 값을 ~

.....

을 반복하면 S의 최솟값을 구할 수 있다는 것을 알 수 있습니다. 

 

그래서 위의 아이디어대로 코드를 작성했습니다. 

 

---

정답률이 높은 문제답게 처음으로 한 번에 통과한 문제(웬일이지)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<int> a, b;
    for (int i = 0; N > i; i++)
    {
        int num;
        cin >> num;
        a.emplace_back(num);
    }
    
    for (int i = 0; N > i; i++)
    {
        int num;
        cin >> num;
        b.emplace_back(num);
    }
    
    int answer = 0;
    
    //a의 최솟값 * b의 최대값
    while (!a.empty())
    {
        auto aMinVal = min_element(a.begin(), a.end());
        auto bMaxVal = max_element(b.begin(), b.end());
        
        answer += *aMinVal * *bMaxVal;
        
        //다음 최솟값과 최댓값을 구해야 하니까 계산이 끝난 원소들은 삭제한다. 
        a.erase(aMinVal);
        b.erase(bMaxVal);
    }
    
    cout << answer;
    
    return 0;
}