1026번 보물 문제를 풀어보았다.
1026 보물
https://www.acmicpc.net/problem/1026
1026번: 보물
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.
www.acmicpc.net
이번 문제는 간단한 탐색 정렬문제이다.
S=A[0]*B[0]+A[1]*B[1]...A[n-1]*B[n-1] 의 수열값이 존재하며, B의 수열은 고정, A의 수열을 재배열하여 S의 최소값을 만드는 문제이다.
시간복잡도가 O(n^2)이 나오겠지만 귀찮으니 하드코딩하여 풀었다.
단순히 B의 최대값을 탐색, A의 최소값과 매치, B의 최대값의 위치를 체크, 체크 안된 다음 최대값을 탐색, 그리고 다시 매치하여 단순 탐색 정렬로 풀었다.
#include <stdio.h>
#include <algorithm>
int main()
{
int i,j,n,s=0,a[51],b[51],c[51],d[51]={0},maxi,wherem;
scanf("%d", &n);
for(i=0; i<n; i++) scanf("%d", &a[i]);
for(i=0; i<n; i++) scanf("%d", &b[i]);
std::sort(a,a+n);
for(i=0; i<n; i++) {
maxi=-1;
wherem=-1;
for(j=0; j<n; j++) {
if(!d[j] && maxi<b[j]) {maxi=b[j];wherem=j;}
}
d[wherem]=1;
c[wherem]=a[i];
}
for(i=0; i<n; i++) s+=c[i]*b[i];
printf("%d",s);
}