58. C++ 백준 1026 번 간단한 풀이, 정석 풀이

안녕하세요. 코딩하는 덕구입니다. C++백준 1026 번 보물 입니다.

그리디 알고리즘 문제입니다.

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

1026번: 보물

 

예를들어 1, 4, 6, 9 라는 숫자가 주어졌을 때

이 숫자들을 두개씩 곱하고, 곱한 수들을 더해서 가장 작게 만들어야 될 때

우리는 직관적으로 가장 큰 수는 가장 작은 수와 곱해야 된다는 것을 알 수 있습니다.

1*9 = 9

4*9 = 36 

6*9 = 54

처럼 큰 수에 큰 수를 곱하면 값이 기하급수적으로 커지기 때문이죠.

 

백준 1026번 C++간단한 풀이입니다.

A를 오름차순으로 정렬 (작은 수 부터 큰 수로)

B를 내림차순으로 정렬 (큰 수 부터 작은수로)

그리고 각 index에 맞춰서 곱 합니다.

가장 작은 수와, 가장 큰 수, 두 번째로 작은 수와, 두 번째로 큰 수....

i 번 째로 작은 수 와  i번 째로 큰 수가 곱해지면서 이 곱들의 합은 최소값이 되겠죠.

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

int main(){
    int N, sum = 0;
    cin >> N;
    int A[51] = {0,};
    int B[51] = {0,};

    for(int i = 0; i<N; i++){
        cin >> A[i];
    }
    for(int i = 0; i<N; i++){
        cin >> B[i];
    }
    sort(A, A+N);
    sort(B, B+N, greater<>());
    for(int i = 0; i<N; i++){
        sum += A[i]*B[i];
    }

    cout << sum;
    return 0;
}

 

백준 1026번 C++최종 코드입니다.

배열 B를 정렬하지 않는 조건을 만족하면서 문제를 풀어야 하므로

최대값과, 최소값을 뽑아서 곱하면 되겠죠.

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

int main(){
    int N, sum = 0, num;
    cin >> N;
    vector<int> A, B;

    for(int i = 0; i<N; i++) {
        cin >> num;
        A.push_back(num);
    }
    for(int i = 0; i<N; i++){
        cin >> num;
        B.push_back(num);
    }
    for(int i = 0; i<N; i++){
        sum += *min_element(A.begin(), A.end()) * *max_element(B.begin(), B.end());
        A.erase(min_element(A.begin(), A.end()));
        B.erase(max_element(B.begin(), B.end()));
    }
    cout << sum;
    return 0;
}

사실 다양한 풀이가 있을 수 있습니다. 예를들어 B의 성분들의 크기 순으로 A의 성분들을 반대로 정렬하면 되겠죠

 

C++ 백준 1026 번 이였습니다. 감사합니다.