C++로 배포할 테디의 총 수 최소화

문제 설명

주어진 N개의 학생 수와 학생들이 얻은 점수를 나타내는 배열. 학교는 테디에게 테디를 대가로 주기로 결정했습니다. 그러나 학교에서는 비용을 절감하고자 하므로 다음과 같은 제약 조건을 부과하여 배포할 테디의 총 수를 최소화합니다. -

• 모든 학생은 적어도 하나의 테디를 받아야 합니다.
• 두 명의 학생이 나란히 앉았다면 더 높은 점수를 받은 학생이 더 많은 점수를 받아야 합니다.
• 두 명의 학생이 같은 점수를 받은 경우 다른 수의 테디를 받을 수 있습니다.

예

3명의 학생이 있고 획득한 점수가 −

arr[] = {2, 3, 3}
So, total number of teddies to be distributed:
{1, 2, 1} i.e. 4 teddies

알고리즘

이 문제는 다음과 같이 동적 프로그래밍을 사용하여 해결할 수 있습니다. -

1. Create a table of size N and initialize it with 1 as each student must get atleast one teddy
2. Iterate over marks array and perform below step:
   a. If current student has more marks than previous student then:
      i. Get the number of teddies given to the previous student
      ii. Increment teddie count by 1
   b. If current student has lesser marks than previous student then:
      i. Review and change all the values assigned earlier

예

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int teddieDistribution(int *marks, int n) {
   int table[n];
   fill(table, table + n, 1);
   for (int i = 0; i < n - 1; ++i) {
      if (marks[i + 1] > marks[i]) {
         table[i + 1] = table[i] + 1;
      } else if (marks[i] > marks[i + 1]) {
         int temp = i;
         while (true) {
            if (temp >= 0 && (marks[temp] >
            marks[temp + 1])) {
               if (table[temp] >
               table[temp + 1]) {
                  --temp;
                  continue;
               } else {
                  table[temp] =
                  table[temp + 1] + 1;
                  --temp;
               }
            } else {
               break;
            }
         }
      }
   }
   int totalTeddies = 0;
   for (int i = 0; i < n; ++i) {
      totalTeddies += table[i];
   }
   return totalTeddies;
}
int main() {
   int marks[] = {2, 6, 5, 2, 3, 7};
   int totalTeddies = teddieDistribution(marks,
   SIZE(marks));
      cout << "Total teddies to be distributed: " <<
   totalTeddies << "\n";
      return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Total teddies to be distributed: 12