[백준/1026/C언어] 보물 _ 풀이

https://www.acmicpc.net/problem/1026

1026번: 보물

---

풀이

#include <stdio.h>

int main() {
	int	n;		// 50까지
	int a[51], b[51];	// a의 배열, b의 배열
	int a_re[51], b_re[51];		// a의 재배열, b의 '원소'재배열(b의 재배열 x)
	int s = 0;		// 최소 합
	int cnt = 0;	

	scanf("%d", &n);	// 길이 입력
	for (int i = 0; i < n; i++)		// a배열 원소 입력
		scanf("%d", &a[i]);		
	for (int i = 0; i < n; i++)		// b배열 원소 입력
		scanf("%d", &b[i]);

	// a_re = a 배열 내림차순
	for (int s = 100; s >= 0; s--) {	// 100에서 0까지 큰수부터 -
		for (int i = 0; i < n; i++) {	
			if (a[i] == s) {		// a[i]와 s가 같을때
				a_re[cnt] = s;		// a_re의 0번째부터 채우기
				cnt++;
			}
		}
	}
	cnt = 0;		// 초기화

	// b_re = b 배열을 오름차순 정렬하기 위한 i를 저장
	for (int s = 0; s <= 100; s++) {	// s를 최소부터 100까지
		for (int i = 0; i < n; i++) {
			if (b[i] == s) {		// b[i]가 s와 같을때
				b_re[cnt] = i;		// b_re의 0번째부터 채우기
				cnt++;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		s += a_re[i] * b[b_re[i]];		// a의 최대값과 b의 최소값을 곱해서 덧셈
	}

	printf("%d\n", s);

	return 0;
}

 

문제의 목표는 S를 가장 작은 값으로 만드는 것이다.

A를 내림차순으로 재배열하고, B를 오름차순으로 재배열해서 곱하고 더하면 쉽게 구할수 있겠지만

본문에서 B는 재배열하지 않는다고 말한다.

 

그렇기 때문에 a_re에는 a를 내림차순으로 재배열시킨것을 저장하고

b_re에는 b배열을 오름차순으로 '참조' 할 수 있게끔 인덱스를 저장한다.