[C++] 백준 1026번 보물

1. 문제이해

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

1026번: 보물

 

길이가 N인 정수 배열 A와 B를 입력받아 S = A[0]×B[0] + ... + A[N-1]×B[N-1] 라고 할때,

S의 최솟값을 구하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

A와 B의 원소들을 곱하여 모두 더해 나온 여러가지 경우의 값들(S) 중 최솟값을 찾아 출력하는 문제이다.

S의 최솟값을 구하기 위해서는, A의 가장 작은 수부터 B의 가장 큰 수와 곱해나가거나,

반대로 A의 가장 큰수와 B의 가장 작은 수를 곱하는 형식으로 짝 지어 나가는 방법이 있다.

즉, A를 오름차순, B를 내림차순으로 정렬하여 곱하거나, A를 내림차순, B를 오름차순으로 정렬하여 곱해야한다.

 

즉, 위의 예제입력과 같이, A가 1 1 1 6 0, B가 2 7 8 3 1인 경우,

A를 오름차순으로 정리하면, 0 1 1 1 6

B를 내림차순으로 정리하면, 8 7 3 2 1

첫번째 항부터 곱해나가면, 0 + 7 + 3 + 2 + 6 = 18, 최솟값으로 18을 출력하게 된다.

 

 

 

3. 소스코드

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

// 내림차순
bool DESC(int a, int b) {
	return a > b;
}

int main() {
	int N;
	int A[100];
	int B[100];
	int sum = 0;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}

	// A를 오름차순, B를 내림차순으로 정렬
	sort(A, A + N);	
	sort(B, B + N, DESC);

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

	cout << sum;

	return 0;
}

구현하는 방법은 간단했다.

위에서 이야기 했듯이 A를 오름차순, B를 내림차순으로 정렬하던지, A를 내림차순, B를 오름차순으로 정렬하고 곱해주면 된다.

나는 전자의 경우를 이용해서 A와 B를 정렬해주고, for 문을 통해 각각의 요소들을 곱하고 더해주었다.

 

 

---

오랜만에 아무런 오류없이 한번에 통과한 문제였다. 🥰

블로그 포스팅을 하고 문제를 다시 보니, B는 정렬하지 말라는 조건이 하나 더 있는데,

백준에서는 오류 없이 잘 돌아갔다..

B를 정렬하지 않고 하려면, A는 정렬하고 B의 원소들 중 최댓값을 찾아나가면서 하나씩 곱해주는 방식을 이용하면 될것같은데,

조만간 시간이 되면 한번 구현해봐야겠다. 😤