제거 작업 후 배열의 축소된 크기를 찾는 C++ 프로그램

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. n개의 양의 정수가 있는 암호가 있다고 가정합니다. 배열에 다음 작업을 적용합니다. 작업은 서로 동일하지 않은 인접한 두 요소를 제거한 다음 합을 해당 위치에 두는 것입니다. 따라서 이 작업은 배열의 크기를 1만큼 줄입니다. 이러한 작업을 수행한 후 배열의 가능한 가장 짧은 길이를 찾아야 합니다.

따라서 입력이 A =[2, 1, 3, 1]과 같으면 출력은 1이 됩니다. 왜냐하면 (1, 3)을 선택하면 배열이 [2, 4, 1]이 되고 다음을 선택하기 때문입니다. (2, 4) 배열을 [6, 1]로 만든 다음 마지막 두 개를 선택하여 [7]을 얻습니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of A
Define one set se
for initialize i := 0, when i < n, update (increase i by 1), do:
   insert A[i] into se
if size of se is same as 1, then:
   return n
Otherwise
   return 1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   int n = A.size();
   set<int> a;
   for (int i = 0; i < n; i++) {
      a.insert(A[i]);
   }
   if (a.size() == 1)
      return n;
   else
      return 1;
}
int main() {
   vector<int> A = { 2, 1, 3, 1 };
   cout << solve(A) << endl;
}

입력

{ 2, 1, 3, 1 }