https://www.acmicpc.net/problem/1026
1026번: 보물
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.
www.acmicpc.net
간단한 정렬 문제이다.
a배열과 b배열의 각 원소를 곱한 값을 모두 더한 값이 최소가 되어야 하는 a배열의 수만 재배열해야 한다.
이 값이 최소가 되기 위해서 a의 가장 큰 값과 b의 가장 작은 값을 곱하고 b의 가장 큰값과 a의 가장 작은 값을 곱해주는 방법을 사용하였다.
a배열만 재배열해야 한다고 문제에 나와있지만, 정답으로 합만 출력하면 되므로 a와 b 모두 정렬해줬다.
a와 b 모두 오름차순으로 정렬 후에 a배열의 맨 앞의 값(최솟값)과 b배열의 맨 뒤의 값(최댓값)을 곱해준다.
a배열의 인덱스는 증가하고 b배열의 인덱스는 감소시켜서 점점 a의 큰 값과 b의 작은 값을 곱하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <algorithm>
using namespace std;
int n, sum;
int a[51];
int b[51];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
//input
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);
//a는 가장 작은 수부터 b는 가장 큰수부터해서 각각 곱해준다.
for (int i = 0, j = n - 1; i < n; i++, j--) {
sum += a[i] * b[j];
}
cout << sum;
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 14889. 스타트와 링크 (0) | 2019.07.06 |
|---|---|
| [BOJ] 3184. 양 (0) | 2019.07.06 |
| [BOJ] 2210. 숫자판 점프 (0) | 2019.07.03 |
| [BOJ] 13458. 시험 감독 (0) | 2019.07.03 |
| [BOJ] 2529. 부등호 (0) | 2019.07.03 |