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

C++에서 합이 같은 두 집합의 최대 합 구하는 방법

숫자 목록 nums가 주어졌을 때, 원소들을 두 집합으로 나누어 각 집합의 합이 서로 같아지도록 만들고, 그중 합이 가장 큰 경우의 값을 구하는 문제입니다.

예를 들어 입력이 nums = [2, 5, 4, 6]이라면 결과는 6이 됩니다. [2, 4]와 [6]이라는 두 집합의 합이 모두 6으로 동일하기 때문입니다.

알고리즘 접근 방식

이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심 아이디어는 두 집합의 합 차이를 DP 테이블의 인덱스로 활용하는 것입니다. 배열의 중심을 전체 합(sum)으로 잡으면, 인덱스 j는 '첫 번째 집합과 두 번째 집합의 합 차이'를 의미하게 됩니다.

구체적인 해결 단계는 다음과 같습니다.

  • 전체 합 sum을 계산합니다.
  • nums의 크기를 n에 저장합니다.
  • (n + 1) × (2 * sum + 5) 크기의 2차원 배열 dp를 선언하고 모든 값을 -1로 초기화합니다. 여기서 -1은 아직 도달하지 못한 상태를 의미합니다.
  • dp[0][sum] = 0으로 설정합니다. 이는 합 차이가 0인 초기 상태를 나타냅니다.
  • i를 1부터 n까지 증가시키며 반복합니다.
    • x = nums[i - 1]로 현재 숫자를 가져옵니다.
    • j를 0부터 2 * sum + 4까지 반복하며 다음 세 가지 경우를 처리합니다.
      • j - x ≥ 0이고 dp[i - 1][j - x] ≠ -1이면, 현재 숫자를 첫 번째 집합에 추가하는 경우로 보고 dp[i][j]를 max(dp[i][j], dp[i - 1][j - x] + x)로 갱신합니다.
      • j + x < 2 * sum + 5이고 dp[i - 1][j + x] ≠ -1이면, 현재 숫자를 두 번째 집합에 추가하는 경우로 보고 dp[i][j]를 max(dp[i][j], dp[i - 1][j + x])로 갱신합니다.
      • 현재 숫자를 어느 집합에도 사용하지 않는 경우도 고려하여 dp[i][j]를 max(dp[i][j], dp[i - 1][j])로 갱신합니다.
  • 모든 반복이 끝나면 dp[n][sum]을 반환합니다. 이 값이 합이 같은 두 집합이 가질 수 있는 최대 합입니다.

C++ 구현 예제

아래 코드를 통해 구현 방법을 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int sum = 0;
      for (int i : nums) sum += i;
      int n = nums.size();
      vector<vector<int> > dp(n + 1, vector<int>(2 * sum + 5, -1));
      dp[0][sum] = 0;
      for (int i = 1; i <= n; i++) {
         int x = nums[i - 1];
         for (int j = 0; j < 2 * sum + 5; j++) {
            if (j - x >= 0 && dp[i - 1][j - x] != -1) {
               dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + x);
            }
            if (j + x < 2 * sum + 5 && dp[i - 1][j + x] != -1) {
               dp[i][j] = max(dp[i][j], dp[i - 1][j + x]);
            }
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
         }
      }
      return dp[n][sum];
   }
};
int solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
main(){
   vector<int> v = {2, 5, 4, 6};
   cout << solve(v);
}

입력

{2, 5, 4, 6}

출력

6