C 백준 1026 보물 (수학)

 

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

 

---

문제

1. 함수 S = A[0] * B[0] + ... + A[N-1] + B[N-1] 의 최소값을 구하는 코드
2. 첫째 줄에 N (0 <= N <= 100) 입력
3. 오름차순으로 정렬 후 곱해서 모두 더함
4. 최솟값 출력

---

 

완성 코드

#include <stdio.h>

void quickSort(int array[], int low, int high) {
	int L = low, H = high;
	if (high < 1) return; //원소 개수가 1개면 바로 출력함

	int pivot = array[(low + high) / 2]; 	//가운데 원소를  기준원소로 삼음

	while (low <= high) {
		while (array[low] < pivot) low++; //기준원소보다 low원소가 작을 때 low를 증가시킨다
		while (array[high] > pivot) high--; //기준원소보다 high원소가 클 때 high를 감소시킨다
		if (low <= high) {
			int tmp = array[low];			//원소를 교환시킨다
			array[low] = array[high];
			array[high] = tmp;
			low++;
			high--;
		}
	} while (low <= high);

	//재귀
	if (L < high)
		quickSort(array, L, high); //왼쪽 배열 재귀

	if (low < H)
		quickSort(array, low, H); //오른쪽 배열 재귀

}

int main(void) {
    int N, sum = 0;
    int A[50], B[50];

    scanf_s("%d", &N);

    for (int i = 0; i < N; i++) { // A 배열을 받는 부분
        scanf_s("%d", &A[i]);
    }
    for (int i = 0; i < N; i++) { // B 배열은 받는 부분
        scanf_s("%d", &B[i]);
    }

	quickSort(A, 0, N - 1); // 오름차순으로 정렬
	quickSort(B, 0, N - 1);

	for (int i = 0, j = N - 1; i < N, j >= 0; i++, j--) { // 큰 수와 작은 수를 순서대로(한 개는 오름차순, 한 개는 내림차순으로)
		sum += A[i] * B[j];
	}

	printf("%d", sum);

    return 0;
}