백준 - 1026 보물

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

1026번: 보물

 

1. 문제 풀이 아이디어

문제의 예제 입력을 통해서 상세히 알아보자. 

5

1 1 1 6 0

2 7 8 3 1 

이것이 입력이다. 

합의 최솟값을 출력하려면 각각 a,b의 곱이 최소여야 한다. 최소를 만드려면 어떻게 하면 될까?

주어진 예제를 가지고 설명해보면, 

a - 0 1 1 1 6 (오름차순)

b - 8 7 3 2 1 (내림차순) 순으로 정렬하면 된다.

 

2. 풀이 코드(C++)

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> v1;
vector <int> v2;

int main(void) {

	int n;
	int sum = 0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v1.push_back(a);
	}
	for (int i = 0; i < n; i++) {
		int b;
		cin >> b;
		v2.push_back(b);
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end(), greater<int>());

	for (int i = 0; i < n; i++) {
		sum = sum + (v1[i] * v2[i]);
	}
	cout << sum;

}

 

3. 배운점

- 벡터에서 v1[i] 이런 방식의 접근도 가능하다.