[BOJ] 백준 1026 보물

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

Approach

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

A가 배치될 수 있는 모든 경우의 수에 대해

A[i] × B[i] 합(=S)의 최소값을 구하면 되는 문제이다.

 

문제 조건을 잘 이용하면 A가 재배치 될 수 있는 모든 Case를 탐색할 필요 없다.

(조건) A, B 각 원소는 100보다 작은 양수 때문에

A[i] × B[i] 합이 최소가 되려면

어느 한쪽(A)은 작은 순서, 다른 한쪽(B)은 큰 순서로 곱해지면 된다.

 

A = [ 1 , 1 , 1 , 6 , 0 ] → 오름차순 → [ 0 , 1 , 1 , 1 , 6 ] 

B = [ 2 , 7 , 8 , 3 , 1 ] → 내림차순 → [ 8 , 7 , 3 , 2 , 1 ]

S = (0 × 8) + (1 × 7) + (1 × 3) + (1 × 2) + (6 × 1)

   = 0 + 7 + 3 + 2 + 6 = 18 

 

문제에서는 B는 재배치 할 수 없다고 했는데

A 배치가 그에 맞게 배치된다고 보면 된다.

A = [ 1 , 1 , 1 , 6 , 0 ] → 재배치 → [ 1 , 1 , 0 , 1 , 6] 

B = [ 2 , 7 , 8 , 3 , 1 ] → 그대로 → [ 2 , 7 , 8 , 3 , 1 ] 

(A가 어떻게 배치되었는지를 요구하지 않기 때문에 가능)

 

C++

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

using namespace std;

int N, val, ans;
vector<int> A, B;

void input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> val;
		A.push_back(val);
	}
	for (int i = 0; i < N; i++)
	{
		cin >> val;
		B.push_back(val);
	}
}

int main() 
{
	// freopen("input.txt", "r", stdin);
	input();

	sort(A.begin(), A.end());   
	sort(B.begin(), B.end(), greater<int>());

	for (int i = 0; i < N; i++) 
	{
		ans = ans + (A[i] * B[i]);
	}
		
	printf("%d\n", ans);
}

 

Java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int A[] = new int[n];
		int B[] = new int[n];
		for(int i=0; i<n; i++){
			A[i] = sc.nextInt();
		}
		
		for(int i=0; i<n; i++){
			B[i] = sc.nextInt();
		}
		re_array1(A, n);
		re_array2(B, n);
		
		int sum = 0;
		for(int i=0; i<n; i++){	
			sum = sum + (A[i]*B[i]);
		}
		System.out.println(sum);
	}
    
	public static int[] re_array1(int[] arr, int n){
		int i, j,temp;
		for(i=n; i>0 ; i--){
			for(j=0; j<i-1; j++){
				if(arr[j] > arr[j+1]){
					temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}	
			}
		}
		return arr;
	}
    
	public static int[] re_array2(int[] arr, int n){
		int i, j,temp;
		for(i=n; i>0 ; i--){
			for(j=0; j<i-1; j++){
				if(arr[j] < arr[j+1]){
					temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}	
			}
		}
		return arr;
	}
}