Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 평균이 같은 두 배열로 분할하기

배열 A가 하나 주어졌다고 가정해 봅시다. 우리는 A의 모든 원소를 리스트 B 또는 리스트 C 중 하나로 옮겨야 합니다(리스트 B와 C는 처음에는 비어 있습니다). 모든 원소를 옮긴 후, B와 C가 모두 비어 있지 않으면서 두 리스트의 평균값이 같아질 수 있는지 확인해야 합니다.

예를 들어 입력이 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이라면 결과는 true입니다.

문제 접근 방법

이 문제의 핵심 아이디어는 간단한 수학적 관계에서 출발합니다. 배열 A의 크기를 n, 전체 합을 total이라 할 때, 어떤 리스트가 k개의 원소를 가져간다면 두 리스트의 평균이 같아지려면 해당 k개 원소의 합이 정확히 total × k ÷ n이 되어야 합니다.

따라서 우리는 "k개의 원소를 선택했을 때 그 합이 total × k ÷ n이 되는 경우가 존재하는가?"라는 질문에 답하면 됩니다. 이는 동적 계획법(DP)을 활용한 부분합(subset sum) 방식으로 효율적으로 확인할 수 있습니다.

알고리즘 단계

  • n := A의 크기, total := 0으로 초기화합니다.
  • i := 0부터 i < n까지 반복하며 total := total + A[i]로 전체 합을 계산합니다.
  • isPossible := false, m := n / 2로 설정합니다.
  • i := 1부터 i <= m이고 isPossible이 거짓인 동안 반복합니다.
    • 만약 total * i mod n이 0이라면 isPossible := true로 설정합니다.
  • isPossible이 여전히 거짓이라면 false를 반환합니다. (평균이 같아지는 경우가 애초에 존재할 수 없음)
  • 크기가 (total + 1) × ((n / 2) + 1)인 2차원 배열 dp를 정의합니다. 여기서 dp[j, l]은 "l개의 원소를 사용하여 합이 j가 되는 부분 집합이 존재하는가?"를 의미합니다.
  • dp[0, 0] := true로 초기화합니다.
  • i := 0부터 i < n까지 반복합니다.
    • x := A[i]
    • j := total부터 j >= x일 때까지 j를 1씩 감소시키며 반복합니다.
      • l := 1부터 l <= (n / 2)일 때까지 l을 1씩 증가시키며 반복합니다.
        • dp[j, l] := dp[j, l] OR dp[j − x, l − 1]
  • i := 1부터 i <= (n / 2)까지 반복합니다.
    • (total * i) mod n이 0이고 dp[total * i / n, i]가 참이라면 true를 반환합니다.
  • false를 반환합니다.

다음 구현 예제를 통해 더 잘 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size();
        int total = 0 ;
        for(int i = 0; i < n; i++) total += A[i];
        bool isPossible = false;
        int m = n / 2;
        for (int i = 1; i <= m && !isPossible; ++i)
        if (total*i%n == 0) isPossible = true;
        if (!isPossible) return false;
        vector < vector <bool> > dp(total + 1, vector <bool>((n / 2) + 1));
        dp[0][0] = true;
        for(int i = 0; i < n; i++){
            int x = A[i];
            for(int j = total; j >= x; j--){
                for(int l = 1; l <= (n / 2); l++){
                    dp[j][l] = dp[j][l] || dp[j - x][l - 1];
                }
            }
        }
        for(int i = 1 ; i <= (n / 2); i++){
            if((total * i) % n == 0 && dp[total * i / n][i]) return true;
        }
        return false;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8,9,10};
    cout << (ob.splitArraySameAverage(v));
}

입력

{1,2,3,4,5,6,7,8,9,10}

출력

1