문제

BOJ 1026, 보물

핵심

• 입력의 크기가 $50$이라 구현에 초점을 맞춘다.
• 배열 A와 B가 있을 때 b를 재배열하지 않고 다음 합계의 최솟값을 구해야 한다.
  $S = A[0] × B[0] + ... + A[N-1] × B[N-1]$
• 두 수의 곱셈의 합이 최솟값이 되려면 가장 큰 수는 가장 작은 수에 곱해야 한다는 명제를 가지고 문제에 접근한다. 최댓값을 최솟값이랑 곱하지 않았을 때 전체 합은 커지기 마련이다. b를 재배열하지 말라고 했으나 b의 인덱스를 다시 사용하지 않으므로 초기 순서를 기억할 필요는 없다.
• 배열 A와 B를 정렬한 뒤 A의 최솟값은 B의 최댓값과 곱하여 최소합을 구한다.

개선

코드

시간복잡도

• $O(N\times logN)$

C++

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

int a[54], b[54];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	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);
	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans += a[i] * b[n - i - 1];
	cout << ans;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> a = new ArrayList<>();
        ArrayList<Integer> b = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            a.add(Integer.parseInt(st.nextToken()));
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            b.add(Integer.parseInt(st.nextToken()));
        a.sort((e1, e2) -> Integer.compare(e1, e2));
        b.sort((e1, e2) -> Integer.compare(e1, e2));
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += a.get(i) * b.get(n - 1 - i);
        System.out.println(ans);
        br.close();
    }
}