[백준] 1026번 보물 c++

1026. 보물 

1026번: 보물

 

 

제출 수가 굉장히 큰 것을 보아, 알고리즘의 기초를 다루는데 있어 의미있는 문제라고 생각한다. 

---

풀이:

 

문제에서 B는 재배열하면 안된다는 조건을 주었지만, 아이러니하게도 해당 알고리즘을 구현하는데 있어서 B의 순서를 바꾸어도 정답에는 아무런 영향이 없다. 

 

우선 주어진 배열의 길이 N은 50보다 작거나 같은 자연수이기 때문에 시간제한은 크게 걱정하지 않아도 된다. 

다만 매번 주의 깊게 살펴볼 것은 문제에서 배열의 원소들이 제시될 때, 이 원소들이 이어서 주어지는지 아님 띄어져서 제시되는 지를 살펴볼 필요가 있다. 제시되는 방법에 따라 입력값을 받는 코드의 형태가 달라지기 때문에 매번 확인 할 필요가 있다. 필자의 경우, 해당 사항을 매번 놓쳐서 전혀다른 곳에서 삽질하는 경우가 많았다 ㅜ

 

다시 보물 문제로 돌아가보자.

문제에서 배열의 주어질 때 해당 배열의 원소가 띄어서주어진다.

때문에 백터 a와 b를 생성하고 각각의 벡터에 주어진 정수들을 저장했다.

for (int i = 0; i < num; i++) {
		cin >> k;
		a.push_back(k);
	}
for (int i = 0; i < num; i++) {
		cin >> k;
		b.push_back(k);
	}

그리고 벡터 a는 원소들을 오름차순으로 정렬하고, 벡터 b는 내림차순으로 정렬했다.

S = A[0]×B[0] + ... + A[N-1]×B[N-1]의 형태인 함수 S의 값을 최소로 만들기 위해서는 a벡터의 가장 작은 정수와 b벡터의 가장 큰 수가 순차적으로 곱해져야하기 때문이다. 

벡터에서 오름차순정렬은 굉장히 쉽다. 바로 sort(v.begin(),v.end())형태의 c++ 표준 라이브러리 함수를 이용한다.

내림차순 정렬도 유사하게 sort(v.rbegin(), v.rend())형태로 r을 붙여 reverse를 나타내거나 reverse(v.begin(),v.end())를 이용하면 쉽게 나타낼 수 있다.

 

sort(a.begin(), a.end());
sort(b.rbegin(), b.rend());

 

마지막으로는 문제에 주어진 S함수만 구현하면 된다.

for()문을 이용하여, a와 b벡터의 원소를 순차적으로 곱해주고 그 값을 새로운 변수 sum에 더해준다.

for (int i = 0; i < num; i++) {
		sum += (a[i] * b[i]);
	}

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> a;
vector<int> b;


int main() {
	ios::sync_with_stdio(0);
	cout.tie(); cin.tie();
	int k;
	int num;
	int sum = 0;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> k;
		a.push_back(k);
	}
	for (int i = 0; i < num; i++) {
		cin >> k;
		b.push_back(k);
	}
	sort(a.begin(), a.end());
	sort(b.rbegin(), b.rend());

	for (int i = 0; i < num; i++) {
		sum += (a[i] * b[i]);
	}

	cout << sum << "\n";
	return 0;


}