이 기사에서는 주어진 n개의 숫자 배열을 재배열하는 문제에 대해 논의할 것입니다. 기본적으로 배열에서 요소를 선택해야 합니다. 각 요소를 선택하기 위해 현재 요소의 값 * 현재 요소보다 먼저 선택된 요소의 수로 평가될 몇 가지 포인트를 얻습니다. 최대 포인트를 얻으려면 요소를 선택해야 합니다. 예를 들어 -
Input : arr[ ] = { 3, 1, 5, 6, 3 }
If we select the elements in the way it is given, our points will be
= 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
= 41
To maximize the points we have to select the elements in order { 1, 3, 3, 5, 6 }
= 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
= 48(maximum)
Output : 48
Input : arr[ ] = { 2, 4, 7, 1, 8 }
Output : 63 해결책을 찾기 위한 접근 방식
예제를 보면 최대 포인트를 얻기 위해 그것을 얻었고 가장 작은 것에서 가장 큰 것까지 요소를 선택해야 합니다. 솔루션을 찾는 접근 방식은,
- 주어진 배열을 오름차순으로 정렬합니다.
- 인덱스 0부터 끝까지 요소 선택 시작
- 각 요소를 선택하여 얻은 점수를 계산합니다.
예시
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main () {
int arr[] = { 2, 4, 7, 1, 8 };
int n = sizeof (arr) / sizeof (arr[0]);
// sorting the array
sort (arr, arr + n);
int points = 0;
// traverse the array and calculate the points
for (int i = 0; i < n; i++) {
points += arr[i] * i;
}
cout << "Maximum points: " << points;
return 0;
} 출력
Maximum points: 63
위 코드 설명
이 C++ 코드는 이해하기 쉽습니다. 먼저 배열을 정렬한 다음 for 루프를 사용하여 배열을 탐색하고 각 요소를 처음부터 끝까지 선택하여 얻은 포인트를 계산합니다.
결론
이 기사에서는 i * arr[i]로 계산되는 포인트의 최대 포인트를 얻기 위해 배열에서 요소를 선택하는 문제에 대해 논의합니다. 이 문제를 해결하고 최대 점수를 얻기 위해 욕심 많은 접근 방식을 적용합니다. 또한 동일한 작업을 수행하는 C++ 코드에 대해 논의합니다. 이 코드는 C, Java, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.