[C++] BOJ 1026번 : 보물

시간제한	메모리제한	알고리즘 분류
2 초	128 MB	수학, 그리디, 정렬

 

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

 

---

문제 해결 조건

수열의 곱 S의 최솟값을 구하기 위해, 배열 A의 수를 재배열한다.

배열 B의 수는 재배열해서는 안된다.

 

해결하기 위한 설계 1차

1. 배열 A의 가장 낮은 수는 B의 가장 큰 수와 곱하고, 배열 A의 가장 큰 수는 배열 B의 가장 낮은 수와 곱한다.  

2. 배열 B의 인덱스 별로, 데이터가 몇 번째로 큰 수인지 저장한다.

3. 배열 A의 수를 B의 정리된 수를 카피한 tmp배열과 곱한뒤 최솟값 s를 구한다?

 

1차 시도의 문제점

문제 해결 조건 상으로 보았을 때, 배열 B의 수는 재배열해서는 안되므로

임시 배열 tmp에 배열 b의 값을 카피하거나 main함수와 solve함수를 구분해 사용한다고 생각했다.

하지만 이는 결론적으로 배열 b를 재배열하는 것과 다르지않다.

 

해결하기 위한 설계 2차

1. 배열 A의 가장 낮은 수는 B의 가장 큰 수와 곱하고, 배열 A의 가장 큰 수는 배열 B의 가장 낮은 수와 곱한다.  (동일)

2. 배열 A와 B모두, 오름 차순으로 정렬. algorithm 헤더의 sort함수를 이용했다.

3. 정렬된 배열 A는 i에서 시작하고, B는 n-i-1에서 시작해 a[i]*b[n-i-1] 반복문을 실행한다.

*  a[i] = 가장 작은 수, b[n-i-1] = 가장 큰 수

 

2차 시도 코드

#include <iostream>
#include <algorithm> 

using namespace std;

int n, ans;
int a[51], b[51];

void solve() {
	//배열 A를 입력받아 오름차순 정렬
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a+n);

	//배열 B를 입력받아 오름차순 정렬
	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}
	sort(b, b+n);

	for (int i = 0; i < n; i++)
	{
		cout << "a[" << i << "] ==" << a[i] << '\t';
		cout << "b[" << n - i -1 << "] ==" << b[n - i -1] << '\n';
		ans += a[i] * b[n - i -1];
	}
	cout << ans << '\n';
}

* 중간에 삽입한 출력을 빼고 제출해야 정답처리됨

 

2차 시도의 결과

* a[i]*b[n-i-1]를 살펴보기 위해 출력문을 중간에 넣었다.

- 예제 출력결과와 동일한 값을 얻을 수 있었다.

다른 풀이

문제에서는 A와 B를 배열이라고 지칭했기에 조건에 따라 배열을 a[51], b[51]이라고 선언하였지만

다른 사람들의 풀이를 살펴보니 벡터로 푸는 사람들도 많았다. 

또, 배열을 정렬할 때 b[n-i-1]처럼 인덱스를 복잡하게 쓰기보다 정렬을 내림차순 정렬, 오름차순 정렬로 구분해 써주면 인덱스를 헷갈리지 않고 쉽게 곱할 수 있다.