[백준 C++] 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의 최솟값을 출력한다.

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

풀이

알고리즘 분류를 보니 그리디알고리즘을 사용한다고 하였는데, 어찌됬던 매선택마다 최선의선택을 하는 알고리즘이라고한다.
먼저 문제 규칙상 가장큰B원소와 가장작은A원소의 곱을 해야하므로,

필자는 A배열을 정리하기위해 그리디알고리즘대신 도수표를 만들었다.

1. 빈도수를 모두 체크하는 numList를 만든다.(최대 원소크기 100이니 101개생성)
2. 크기가 가변적인 벡터로구현된 A배열,
   재배열된 A를 저장할 relocation_A,
   배열B를 복사한 compare_B를 정의
3. numList[i] 는 숫자 i에 대한 빈도수로, 100부터 0까지탐색하여 빈도수가 0이될때까지 아래를 시행한다.
   -compare_B에서 숫자i를 찾는다.
   -벡터A의 최솟값을 찾아서(찾은후 해당원소 삭제) relocation_A에 현재 comapre_B와 같은 인덱스 위치에 넣는다.
   -compare_B의 현재원소를 삭제한다.
   -당연히 빈도수 -1

이경우 최악의경우가 A, B의모든원소가 100이면,

100 x 100 x 50(최대N) = 50만 이니 int로 표시가능하다.

아래는 전체코드이다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using namespace std;
//numList는 0~ 100까지 숫자의 빈도수를 나타냄
vector<int> A;
int N, * B, numList[101] = {}; 
int* relocation_A, * compare_B;

void init() { //초기설정
	relocation_A = new int[N];
	compare_B = new int[N];
	B = new int[N];
	for (int i = 0, temp; i < N; i++) {
		scanf("%d", &temp);
		A.push_back(temp);
	}
	for (int i = 0, temp; i < N; i++) {
		scanf("%d", &temp);
		B[i] = temp; //결괏값계산용 B
		compare_B[i] = temp; //비교용 B
	}
	for (int i = 0; i < N; i++) //빈도수카운트
		numList[B[i]]++; //해당숫자의 빈도수를 + 1
}

int find_min() { //A 배열중 최솟값을 찾아 원소를 삭제후 리턴(pop)
	int min = 0x7fffffff;
	int min_index = 0;
	for (int i = 0; i < A.size(); i++) { //A크기만큼
		if (min > A[i]) {
			min = A[i]; //최솟값갱신
			min_index = i;
		}
	}
	A.erase(A.begin() + min_index);  //해당원소를 지움
	return min;
}

void relocation() { //A배열을 재배치하는함수
	//i : 현재숫자
	for (int i = 100; i >= 0; i--) { //모든 빈도수를 체크
		while (numList[i] > 0) { //빈도수전부..
			for (int j = 0; j < N; j++) { //비교B배열 탐색
				//비교B배열중 현재숫자를 찾음
				if (compare_B[j] == i) { 
					int element = find_min(); //A배열에서 현재 최솟값을 찾음
					//재배열된 A배열에 B와 같은 인덱스에 값을 넣음
					relocation_A[j] = element;
					numList[i]--; //현재숫자 빈도수 감소
					compare_B[j] = -1; //비교 B배열 값삭제
				}
			}
		}
	}
}

void printAll() {
	int s = 0;
	for (int i = 0; i < N; i++) 
		s += relocation_A[i] * B[i];
	printf("%d", s);
}

int main(void) {
	scanf("%d", &N);
	init();
	relocation();
	printAll();

	return 0;
}