백준 1026 보물 / C++

문제 : 1026

풀이 point

그리디를 활용하는 문제
s의 값을 가장 작게 만드는 문제이다.

인덱스 순서대로 a[0] x b[0]을 하는 구조이므로 가장 작게 만들기 위해서는 정수 배열 a의 가장 작은수와 b 배열의 가장 큰수를 곱해주면 된다.

이는 수학적으로 쉽게 증명됨

풀이 방법

문제에서 b배열은 재배열하면 안된다고 했지만 무시하고 재배열 해도 된다.(어차피 합은 같기 때문)
a, b 모두 정렬한 후
a배열은 순서대로, b배열은 역순으로 곱해주면 가장 최소가 된다.

코드

//1026, 보물

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

int main(){
    int N;
    std::cin >> N;
    int a[N];
    int b[N];
    for(int i{0}; i<N; ++i) std::cin >> a[i];
    for(int i{0}; i<N; ++i) std::cin >> b[i];

    std::sort(a, a+N);
    std::sort(b, b+N);
    int s{0};
    for(int i{1}; i<=N; ++i)
        s += a[i-1] * b[N-i];
    
    std::cout << s;
    return 0;
}

2025-01-11T01:55:50.695Z