백준 1026 c++ "보물" -PlusUltraCode-

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

 

[필자 사고]

A만 움직여서 B와의 곱이 최소가 되게 만들어라 재미난 문제였다.

B를 움직이지 말아야 되나?? 그럴 필요 없다.

B를 내림차순 정렬하고 A를 오름차순 정렬하여 두 수를 곱하면 된다. 

 

아래는 자세한 코드 해설이다.

[코드 해설]

cmp 함수

• bool cmp(int a, int b)
• 정렬 기준을 정의하는 함수입니다.
• a > b를 반환하므로, 내림차순 정렬을 수행할 때 사용됩니다.

---

Input 함수

• 입력을 받는 역할입니다.

1. 정수 N(배열의 크기)을 입력받음.
2. A 벡터에 N개의 정수를 입력받아 저장.
3. B 벡터에도 N개의 정수를 입력받아 저장.
4. B는 cmp 함수를 이용해 내림차순 정렬, A는 기본 정렬로 오름차순 정렬을 합니다.

 즉, A는 작은 값부터, B는 큰 값부터 정렬합니다.

---

Game_Start 함수

• 두 벡터의 원소를 곱해서 합을 구하는 역할입니다.

1. for문으로 0부터 N-1까지 반복.
2. A[i] * B[i] 값을 계속 더합니다.
3. 최종적으로 합계를 출력합니다.

 이렇게 하면 A의 가장 작은 값과 B의 가장 큰 값이 곱해지고, 그 다음 작은 값과 큰 값이 짝지어져, 결과적으로 합계가 최소가 됩니다.

---

main 함수

1. Input()을 호출하여 입력 및 정렬 수행.
2. Game_Start()를 호출하여 최소 합을 계산하고 출력.

[소스 코드]

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

int N;
vector<int> A;
vector<int> B;

bool cmp(int a, int b) {
	return a > b;
}

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		A.push_back(num);
	}

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		B.push_back(num);
	}
	sort(B.begin(), B.end(), cmp);
	sort(A.begin(), A.end());
}

void Game_Start() {
	int sum = 0;
	for (int i = 0; i < N; i++) {
		sum += A[i] * B[i];
	}
	cout << sum;
}

int main(void) {
	Input();
	Game_Start();
}