[백준] 1026 번 : 보물 / C++

[문제]

문제 :

 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 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의 최솟값을 출력한다.

 

[코드 풀이]

[실패한 코딩]

 

[성공한 코딩]

 여기서 B에 있는 수는 재배열하면 안 된다는 것은 B에 있는 수가 기준이 되도록 하라는 힌트로 보았다. 그리고, B에 있는 수도 정렬해서 재배열해버렸다. 그래도 풀 수 있으면 그만이니까

 

B 배열의 수에 크기 순으로 큰 거는 A 배열의 수에서 크기 순으로 작은 거를 곱하게 만들면 S의 수가 작아지게 된다.

 

이를 토대로, A는 오름차순으로 정렬, B는 내림차순으로 정렬하고, S를 구하도록 했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int cnt;
	int num;
	int total = 0;

	cin >> cnt;

	int* a = new int[cnt];
	int* b = new int[cnt];

	for (int i = 0; i < cnt; i++) {
		cin >> num;
		a[i] = num;
	}
	for (int i = 0; i < cnt; i++) {
		
		cin >> num;
		b[i] = num;
	}

	sort(a, a + cnt,less<int>());
	sort(b, b + cnt,greater<int>());

	for (int i = 0; i < cnt; i++) {
		total += a[i] * b[i];
	}
	
	cout << total;

	return 0;
}

 

[후기 및 배운 점]

이것도 그리디 알고리즘. 정렬을 통해서 쉽게 풀 수 있었다. S의 값이 적게 하는 수학적 근거를 통해서 풀 수 있었다.

 

#C++ 배열의 정렬은 내림차순으로 할 때는 sort(배열의 포인터, 배열의 포인터 + 배열의 크기, less<자료형 타입>()) 을 이용하고, 오름차순으로 할 때는 sort(배열의 포인터, 배열의 포인터 + 배열의 크기, greater<자료형 타입>()) 를 이용한다.

 

#수학 공부를 해야하나..