[BOJ] 1026번 보물 (C++)

 

[BOJ] 1026번 보물 (C++)

---

 

문제링크

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

1026번: 보물

---

풀이방법

백준 풀이 ! 
문제는 정말 정말 간단하다.
배열 두개가 있는데 얘네들 순서를 바꿀수있고, 그 배열 두개를 곱해서 나온 값이 최소가 되도록 하면 끝!
 
근데 잘보면 여기 문제에 함정(?)이 있다.
문제에 설명을 보면 이러한데..

S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

 

잘 보면 A를 배열한다는 얘기는 A의 배열 순서가 마음대로 바뀔수있다는 말이고, 결과값으로 순서를 원하는 것이 아니기 때문에 결국 B도 순서를 바꿀수있다는 얘기와 같다.
그래서 결론은 A B 배열의 순서를 잘 뒤섞은후에 같은 인덱스를 가진 배열끼리 곱해서 더한값이 최소면 된다는것.
일단 제일 먼저 생각 가능한 부분은 단순히 무식하게 B배열을 고정시키고 A배열의 모든 순열 조합을 만들어가면서 곱의 합값을 구해서 완탐하는 방법이다.
그러나 이렇게 풀면 바로 시간초과.
그럼 최소값은 어떻게 구할건가? 
예시를 1개 생각해봅시다.
A[3] = {1,2,3} / B[3] = {1,2,3}
이 두개의 배열로 곱의 최소값을 만들려면 어떻게 할까?
1x1 + 2x2+ 3x3 = 14
1x2 + 2x1 + 3x3 = 13
...
1x3 + 2x2 + 3x1 = 10
모든 경우의 수를 다해보면 빨간 글자 부분만 최소값인걸 알수있다.
이걸 다시 정리하면 A배열의 제일작은수 x B배열의 제일큰수 + A배열의 2번째로 작은수 x B배열의 2번째로 큰수 .. 의 조합으로 만든 합이 제일 작은 결과를 낸다는것을 알수있다.
그럼 하나는 오름차순 정렬, 하나는 내림차순 정렬후에 서로 곱해주고 더해주면 최소값이라는걸 알수있다! 

 

소스코드

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

int N;	//50이하
int A[50];
int	B[50];

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

	return sum;
}

int main() {

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	for (int i = 0; i < N; i++) {
		scanf("%d", &B[i]);
	}

	printf("%d", solve());
	return 0;
}