[백준알고리즘] 1026번: 보물 -C++

[백준알고리즘] 1026번: 보물 -C++

1026번: 보물 (acmicpc.net)

1026번: 보물

음 뭔가 브루트포스로 돌리면서 어려울 것 같았는데, 실상은 그렇지 않았다.

 

정답률이 보장하는 쉬운 문제였던 것 같다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제는 A 배열과 B 배열을 정렬해서 각 원소의 곱의 합이 최소가 되도록 만들면 된다.

 

문제에서는 B 배열의 순서를 이동시킬 수 없다고 해서 변수 명도 \(vecNonVariable\)로 잡기는 했지만, 결국 A 배열만 움직이든 같이 움직이든 상관이 없다. 구해야 할 결과 값은 각 원소의 곱의 합이기 때문인데, 합은 교환 법칙이 성립하기 때문이다.

 

따라서, 두 배열을 모두 정렬시켜주었다. 정렬시켜주는 이유는 간단하다. 작은 수와 큰 수의 곱을 만들어야 합이 최소가 되기 때문이다.

간단한 예제로 살펴보도록 하면 다음과 같다.

 

• A : { 1, 50 }
• B : { 1, 100 }

 

위와 같이 각각의 크기가 2인 배열을 두어 간단한 예제를 살펴보도록 하자. 이 두 배열 A와 B의 곱의 합이 최소가 되는 경우를 보기 위해 두 개의 경우를 살펴볼 것이다. 

하나는 작은 수끼리 곱셈, 큰 수끼리 곱셈을 한 뒤 합하는 방법이다. 다른 하나는 서로 작은 수와 큰 수를 번갈아 곱하고 더하는 방법이다.

 

첫 번째, 작은 수끼리 곱셈, 큰 수끼리 곱셈을 한 뒤 합을 하면 다음과 같은 \(S_1\)이 나온다.

\( S_1 = 1 * 1 + 50 * 100 = 5001 \)

 

두 번째, 작은 수와 큰 수를 번갈아 교차해 곱한 뒤 합을 구하면 다음과 같은 \(S_2\)가 나온다.

\( S_2 = 1 * 100 + 50 * 1 = 150 \)

 

즉, 작은 수와 큰 수를 서로 곱해주어야 나중에 배열의 최종합이 작게 나온다. 비록, 크기가 2인 간단한 배열을 가지고 예를 들었지만, 조금 더 큰 배열을 생각하더라도 조금만 더 생각해보면 그래야 한다는 것을 알 수 있다

수학적으로 항상 그런지는 증명하기는... 모르겠다!

 

여하튼 위의 방법으로 풀이를 하게 되면 아래의 코드가 된다.

std::greater<>()를 이용해 \(vecVariable\)은 내림차순으로 정렬을 했으며, std::less <>()를 이용해 \(vecNonVariable\)은 오름차순으로 정렬했다. std::less <>()를 사용한 오름차순 정렬은 std::sort의 디폴트 설정 값이다.

#include <iostream>
#include <vector>
#include <algorithm>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	
	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<int> vecVariable(n);
	std::vector<int> vecNonVariable(n);

	for (int i = 0; i < n; i++)
		std::cin >> vecVariable[i];
	for (int i = 0; i < n; i++)
		std::cin >> vecNonVariable[i];

	std::sort(vecVariable.begin(), vecVariable.end(), std::greater<>());
	std::sort(vecNonVariable.begin(), vecNonVariable.end(), std::less<>());

	int answer = 0;
	for (int i = 0; i < n; i++)
		answer += (vecVariable[i] * vecNonVariable[i]);

	std::cout << answer;
}