[백준 알고리즘] 1026번 보물

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

1026번: 보물

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]*B[0] + ... + A[N-1]*B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

 

풀이

전제 조건이 B에 있는 수는 재배열하면 안된다.

하지만 B 배열의 값이 큰 것에 A 배열의 값이 제일 작은 수를 곱해주면 된다. 즉 B를 오름차순 또는 내림 차순 정리로 배열 정렬을 바꾸어 A 정렬은 그 역 정렬로 대입하여 곱하면 된다.

 

즉 B의 배열은 정렬이 되어 바꿀 수 있겠지만 단순히 생각했을 때 B의 제일 근 값에 A의 제일 작은 값을 곱해주면 되는 것이다.

 

일단 B를 정렬해보자.

하지만 정렬은 어려가지 방법이 있다. 퀵정렬, 합병 정렬, 버블 정렬 등 여러가지가 많은 데 난 이 중 퀵정렬을 쓸 것이다. 퀵정렬 빅오표기 낮은 이유는 O(n^2) 최악의 상황는 주어진 배열이 역 정렬이 되어 있었을 때이고 그럴 가능성은 작기 때문에 대부분의 케이스에서는 O(nlogn) 정도의 시간 복잡도를 가지게 된다.

 

#include<stdio.h>
#include<algorithm>

using namespace std;
bool desc(int a, int b) {

	return a > b;
}

bool incre(int a, int b) {

	return a < b;
}
int main() {

	int Num = 0;
	scanf("%d", &Num);

	int Aarray[50];
	int Barray[50];

	int Number = 2;
	int count = 0;


		for (int i = 0; i < Num; i++) {

			int temp = 0;
			scanf("%d", &temp);
			Aarray[i] = temp;

		}

		for (int i = 0; i < Num; i++) {

			int temp = 0;
			scanf("%d", &temp);
			Barray[i] = temp;

		}





	sort(Aarray, Aarray + Num,desc );
	sort(Barray, Barray + Num, incre);

	for (int i = 0; i < Num; i++) {

		//printf("%d %d\n", Aarray[i], Barray[i]);
		int temp = Aarray[i] * Barray[i];
		count += temp;
	}
	//A는 내림차순 정리로 하고
	//B는 오름차순 정리로 하고
	//곱하면 제일 작은수



	printf("%d\n", count);

}

끝.