백준, BOJ, 2217번 C++ [CPP]

정말 느낌대로 풀면 되는 풀이지만

검증을 해야한다 사실..

 

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

 

---

 

#맞은 풀이

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

using namespace std;

int N;

vector<int> vec;
vector<int> target;

int main(){
    cin >> N;
    //A숫자
    for(int i = 1; i<=N; i++){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    //B숫자 
    for(int i = 1; i <= N; i++){
        int b;
        cin >> b;
        target.push_back(b);
    }
    
    sort(target.begin(), target.end()); // 오름차순
    sort(vec.begin(), vec.end()); // 오름차순
    reverse(vec.begin(),vec.end()); // 내림차순
    
    int sum = 0;
    
    for(int i = 0; i<N; i++){
        sum += vec[i] * target[i];    
    }
    
    cout << sum <<'\n';
    
    
}

 

여기 아이디어는

큰 숫자를 곱할 때 작은 숫자와 곱해야 작아진다. 라는 간단한 생각으로 풀었다.

모든 숫자에 대해 최소의 값을 더해주면 모두 더한 것도 최소라고 생각해서 풀었다.

 

가장 큰 숫자에는 가장 작은 숫자를 곱해야 해당 숫자로 만들 수 있는 가장 작은 숫자가 되고

나머지에서 또 가장 큰 숫자와 가장 작은 숫자... 계속하면 된다.

 

약간 나눠서 정답인 것은 합쳐도 정답이다.라는 느낌이다.

Divide & Conquer

 

 

아무튼 실제로 생각해보면 그렇다.