[BOJ/백준 1026][C++] 보물

문제

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

 

문제 내용

정수 배열 A와 B의 원소의 곱이 최소가 되도록 하는 함수 S를 만드는 문제이다.

 

문제 풀이

문제에는 배열 B를 재배열하지 말라고 되어있다. 
하지만 굳이 문제를 그렇게 풀 필요는 없어 보인다.
(B를 기준으로 A를 맞추는 건 너무 일이 많아 보인다....)

배열 A와 B 모두 정렬하여, A는 앞에서부터, B는 뒤에서부터 곱하여 더한다면 S의 값이 최소가 된다.

 

코드

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n,tmp;
	cin >> n;
	vector<int>v1; vector<int>v2;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v1.push_back(tmp);
	}
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v2.push_back(tmp);
	}

	//문제 해결
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end()); 
	//배열B는 재배열 하지 말라고 되어있지만, 굳이..?

	int result = 0;
	for (int i = 0; i < n; i++) {
		result = result + v1[i] * v2[n-i-1];
	}
	
	//결과 출력
	cout << result << '\n';
}

 

문제 코드 설명

1) 입력

배열의 길이 n과 배열 v1, v2를 vector로 입력받는다.

 

2) 문제 해결

입력받은 배열 2개를 모두 정렬하고, 하나는 앞에서부터, 나머지 하나는 뒤에서부터 곱하여 더한다.