[Algorithm] 백준 1026번 : 보물 (C++)

문제 링크 : https://www.acmicpc.net/problem/1026

1026번: 보물

---

[문제]

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

길이가 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[0] × B[0] + ... + A[N-1] × B[N-1] 일때 S의 값을 가장 작게 만들려면 큰 숫자일 수록 작은 값을 곱하도록, 즉, A배열의 값들을 작은 순서대로 큰 값의 인덱스로 위치시켜야 한다는 것이다.

본인은 구조체를 선언해 B배열의 값과 인덱스를 복사한 뒤, 값을 기준으로 정렬(내림차순)을 해서 큰 값 순서대로 인덱스를 나열되게끔 하고, A배열에는 정렬(오름차순)을 수행했다.

그 뒤, 반복문으로 이들을 i번째부터 순서대로 곱하여 S에 더해나가면 해답을 구할 수 있다.

[정답 코드]

#include <bits/stdc++.h>
using namespace std;
int N,A[50],B[50],C[50],s=0;

struct El{int val;int idx;};
bool comp(const El& a,const El& b) {return a.val>b.val;}

int main() {
	cin >> N;
	vector<El> Arr(N);
	for(int i=0;i<N;i++) cin >> A[i];
	for(int i=0;i<N;i++) cin >> B[i];

  for (int i=0;i<N;i++) {
    Arr[i].val=B[i];
    Arr[i].idx=i;	
  }
	sort(A,A+N); sort(Arr.begin(),Arr.end(),comp);
	for(int i=0;i<N;i++) s+=B[Arr[i].idx]*A[i];
	cout << s << '\n';
}

[결과]