[C언어/그리디]1026 : 보물

 

문제 접근

B를 재배열하면 안된다.

-> B배열 인자들의 크기 순서를 알 수 있는 새 배열을 만들어 볼까 했지만 효율적이면서 적절한 방법 없음.

A만 오름차순으로 재배열한 후에 A[i]에 접근할 때마다 B에서 첫번째로 큰 값, 두번째로 큰 값, 세번째로 큰값 등을 찾는다.

#include<stdio.h>
#include<stdlib.h>   
#define MAX 55
int compare(const void *a, const void *b)    
{
    int num1 = *(int *)a;    
    int num2 = *(int *)b;    
    if (num1 < num2)  
        return -1;      
    if (num1 > num2)    
        return 1;           
    return 0;    
}

int main(void){
	int n,i,k,chk,max,sum=0;
	int a[MAX]={0},b[MAX]={0},visit[MAX]={0};
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(i=0;i<n;i++)
		scanf("%d",&b[i]);
	qsort(a,n,sizeof(int),compare);
	
	for(i=0;i<n;i++){
		max=-1; //0~100 범위의 값을 가질 수 있으므로 -1로 초기화한다.
		for(k=0;k<n;k++){
			if(visit[k]==0 && max<b[k]){ //visit배열은 첫번째로 큰 값, 두번째로 큰 값 등을 찾을때 필요하다.
				max=b[k];
				chk=k;
			}
		}
		visit[chk]=1;
		sum+=max*a[i];
	}
	
	printf("%d",sum);
}