백준 1026번 보물 C++ 풀이

🔷 백준 1026번 보물 C++ 풀이

🔷 문제 설명

문제

길이가 \(N\)인 두 개의 정수 배열 \(A\), \(B\)가 있습니다. 아래와 같이 \(S\)라는 값을 정의합니다.

\[ S = A[0] \times B[0] + A[1] \times B[1] + \cdots + A[N-1] \times B[N-1] \]

이때, 배열 \(A\)의 원소들을 재배열하여 \(S\)의 값을 최소화해야 합니다. 배열 \(B\)는 재배열할 수 없습니다.

입력

• 첫째 줄: 배열의 길이 \(N\) (\(1 \leq N \leq 50\))
• 둘째 줄: 배열 \(A\)의 \(N\)개의 원소 (각각 \(0 \leq A[i] \leq 100\))
• 셋째 줄: 배열 \(B\)의 \(N\)개의 원소 (각각 \(0 \leq B[i] \leq 100\))

출력

• \(S\)의 최소값을 출력합니다.

🔷 테스트케이스

입력 예시 1

5
1 1 1 6 0
2 7 8 3 1

출력 예시 1

18

입력 예시 2

3
1 1 3
10 30 20

출력 예시 2

80

입력 예시 3

9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1

출력 예시 3

528

🔷 문제설명

만약 \(A\)와 \(B\)를 그대로 곱하면 최소가 되지 않는 경우가 생깁니다. 예를 들어 \(A = [3, 1]\), \(B = [100, 1]\)이면 그대로 곱하면 \(3×100 + 1×1 = 301\)인데 \(A\)를 재배열하여 \(A = [1, 3]\)로 하면 \(1×100 + 3×1 = 103\)로 훨씬 작아집니다. 즉, 큰 수에 작은 수를 곱하고, 작은 수에 큰 수를 곱하는 방식으로 최소를 만들어야 합니다.

🔷 아이디어

• 배열 \(B\)는 고정이므로 \(B\)에서 큰 수는 가급적 작은 수와 곱해야 합니다.
• 따라서:
  • 배열 \(A\)는 오름차순(작은 순서)으로 정렬합니다.
  • 배열 \(B\)는 내림차순(큰 순서)으로 정렬한 복사본을 임시로 사용합니다.
  • 두 배열의 같은 인덱스끼리 곱하여 모두 더하면 최소의 \(S\)를 얻습니다.

🔷 전체 코드 C++

#include <iostream>
#include <queue>

using namespace std;

int compare1(const void* a, const void* b) {
	int x = *(int*)a;
	int y = *(int*)b;
	return x - y;
}
int compare2(const void* a, const void* b) {
	int x = *(int*)a;
	int y = *(int*)b;
	return y - x;
}

int main(void)
{
	int N, sum = 0;
	cin >> N;

	int arr1[100];
	int arr2[100];

	for (int i = 0; i < N; i++)
		cin >> arr1[i];
	for (int i = 0; i < N; i++)
		cin >> arr2[i];

	qsort(arr1, N, sizeof(int), compare1); // A는 오름차순
	qsort(arr2, N, sizeof(int), compare2); // B는 내림차순

	for (int i = 0; i < N; i++)
		sum += arr1[i] * arr2[i];

	cout << sum << endl;

	return 0;
}

🔷 개별 코드 설명

입력 처리

int N;
cin >> N;

int arr1[100];
int arr2[100];

for (int i = 0; i < N; i++)
	cin >> arr1[i];
for (int i = 0; i < N; i++)
	cin >> arr2[i];

배열 길이 \(N\)을 입력받고, \(A\)와 \(B\)의 값들을 차례로 입력받습니다. 배열의 최대 길이는 50이므로 넉넉하게 100으로 선언했습니다.

정렬

qsort(arr1, N, sizeof(int), compare1); // A 오름차순
qsort(arr2, N, sizeof(int), compare2); // B 내림차순

\(A\)는 작은 값부터 차례로 나오도록 오름차순 정렬합니다. \(B\)는 큰 값부터 나오도록 내림차순 정렬한 복사본을 사용합니다. 이렇게 하면 작은 값과 큰 값이 곱해지도록 하여 \(S\)를 최소로 합니다.

합산

int sum = 0;
for (int i = 0; i < N; i++)
	sum += arr1[i] * arr2[i];

정렬된 \(A\)와 \(B\)의 같은 인덱스끼리 곱해 모두 더하면 최소의 \(S\)가 됩니다.

출력

cout << sum << endl;

최종 \(S\)의 최소값을 출력합니다.

🔷 결론

• \(A\)와 \(B\)는 각각 오름차순, 내림차순으로 정렬하여 곱해야 최소의 합이 나옵니다.
• \(B\)는 고정이므로 \(A\)만 재배열하는 것이 핵심입니다.
• 정렬 후 같은 인덱스끼리 곱하면 됩니다.
• 시간 복잡도는 \(O(N\log N)\)로 \(N \leq 50\)이므로 충분히 빠릅니다.

✅ 배열 \(A\)는 작은 수부터, 배열 \(B\)는 큰 수부터 배치
✅ 같은 위치끼리 곱해 합산
✅ \(B\)는 재배열 불가, \(A\)만 정렬 가능
✅ 정렬만 하면 로직은 간단합니다.