임의의 크기를 가진 양의 정수형 배열 arr[]가 주어졌을 때, 각 요소를 인접한(교대하는) 요소와 곱한 뒤 그 결과값들을 모두 더했을 때 합이 최소가 되도록 배열을 재정렬하는 것이 과제입니다.
다양한 입력·출력 시나리오 살펴보기
입력 − int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}
출력 − 연속 쌍 요소의 곱의 합이 최소(7)가 되도록 배열을 재정렬한 결과: 7 0 5 0 5 1 2 1
설명 − 크기가 8인 정수 배열이 주어집니다. 이를 7 0 5 0 5 1 2 1로 재정렬한 후 최소합이 반환되는지 확인합니다. 즉, 7 * 0 + 5 * 0 + 5 * 1 + 2 * 1 = 0 + 0 + 5 + 2 = 7이 됩니다.
입력 − int arr[] = {1, 3, 7, 2, 4, 3}
출력 − 연속 쌍 요소의 곱의 합이 최소(24)가 되도록 배열을 재정렬한 결과: 7 1 4 2 3 3
설명 − 크기가 6인 정수 배열이 주어집니다. 이를 7 1 4 2 3 3으로 재정렬한 후 최소합이 반환되는지 확인합니다. 즉, 7 * 1 + 4 * 2 + 3 * 3 = 7 + 8 + 9 = 24가 됩니다.
프로그램에 적용된 접근 방식
정수형 요소로 구성된 배열을 입력받고 배열의 크기를 계산합니다.
C++ STL의 sort 메서드를 사용하여 배열과 배열의 크기를 sort 함수에 전달해 배열을 오름차순으로 정렬합니다.
정수 변수를 선언하고 Rearrange_min_sum(arr, size) 함수의 호출 결과로 초기화합니다.
Rearrange_min_sum(arr, size) 함수 내부에서는 다음과 같이 동작합니다.
정수 값을 저장하는 벡터 'even'과 'odd'를 생성합니다.
변수 temp와 total을 선언하고 0으로 초기화합니다.
i를 0부터 size보다 작을 때까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 i가 size/2보다 작으면 arr[i]를 odd 벡터에 push하고, 그렇지 않으면 even 벡터에 push합니다.
even.begin(), even.end()와 greater<int>()를 전달하여 sort 메서드를 호출해 even 벡터를 내림차순으로 정렬합니다.
j를 0부터 even.size()보다 작을 때까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 arr[temp++]에 even[j]를, arr[temp++]에 odd[j]를 대입하고, total에 even[j] * odd[j]를 누적합니다.
total을 반환합니다.
결과를 출력합니다.
예제
#include <bits/stdc++.h>
using namespace std;
int Rearrange_min_sum(int arr[], int size){
vector<int> even, odd;
int temp = 0;
int total = 0;
for(int i = 0; i < size; i++){
if (i < size/2){
odd.push_back(arr[i]);
}
else{
even.push_back(arr[i]);
}
}
sort(even.begin(), even.end(), greater<int>());
for(int j = 0; j < even.size(); j++){
arr[temp++] = even[j];
arr[temp++] = odd[j];
total += even[j] * odd[j];
}
return total;
}
int main(){
int arr[] = { 2, 5, 1, 7, 5, 0, 1, 0};
int size = sizeof(arr)/sizeof(arr[0]);
//배열 정렬
sort(arr, arr + size);
//함수 호출
int total = Rearrange_min_sum(arr, size);
cout<<"연속 쌍 요소의 곱의 합이 최소("<<total<<")가 되도록 배열을 재정렬한 결과: ";
for(int i = 0; i < size; i++){
cout << arr[i] << " ";
}
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
연속 쌍 요소의 곱의 합이 최소(7)가 되도록 배열을 재정렬한 결과: 7 0 5 0 5 1 2 1