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

C++로 푸는 1과 0 문제: 동적 계획법으로 최대 문자열 개수 구하기

문제 개요

0을 m개, 1을 n개 가지고 있다고 가정해 보겠습니다. 그리고 이진수(0과 1)로만 이루어진 문자열 배열이 하나 주어집니다. 목표는 주어진 m개의 0과 n개의 1을 사용해 만들 수 있는 문자열의 최대 개수를 구하는 것이며, 각 0과 1은 최대 한 번씩만 사용할 수 있습니다.

예를 들어 배열이 ["10", "0001", "111001", "1", "0"]이고 m = 5, n = 3이라면 정답은 4입니다. 5개의 0과 3개의 1로 "10", "0001", "1", "0"이라는 네 개의 문자열을 만들 수 있기 때문입니다.

풀이 접근 방식

이 문제는 동적 계획법(DP)으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 2차원 DP 테이블을 만들어, 0과 1의 잔여 개수 조합별로 만들 수 있는 문자열의 최대 개수를 누적 기록하는 것입니다. 전체 절차는 다음과 같습니다.

  1. (m + 1) × (n + 1) 크기의 2차원 dp 배열을 생성하고 0으로 초기화합니다.
  2. 결괏값을 담을 ret을 0으로 설정합니다.
  3. 배열의 각 문자열에 대해 다음을 반복합니다.
    • 현재 문자열에서 1의 개수(one)와 0의 개수(zero)를 셉니다.
    • j를 m부터 zero까지, k를 n부터 one까지 역방향으로 순회하며 다음 점화식을 적용합니다.
      dp[j][k] = max(dp[j][k], 1 + dp[j − zero][k − one])
      동시에 ret = max(ret, dp[j][k])로 갱신합니다.
  4. 모든 문자열을 처리한 후 ret을 반환합니다.

내부 루프를 뒤에서 앞으로(역방향) 도는 이유는 같은 문자열이 하나의 상태에서 중복 사용되는 것을 막기 위해서입니다. 이는 배낭(Knapsack) 문제류 DP에서 널리 쓰이는 표준 기법입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int findMaxForm(vector<string>& strs, int m, int n) {
      vector < vector <int> > dp(m + 1, vector <int>(n + 1));
      int ret = 0;
      for(int i = 0; i < strs.size(); i++){
         int one = 0;
         int zero = 0;
         for(int j = 0; j < strs[i].size(); j++){
            one += strs[i][j] == '1';
            zero += strs[i][j] == '0';
         }
         for(int j = m; j>= zero; j--){
            for(int k = n; k >= one; k--){
               dp[j][k] = max(dp[j][k], 1 + dp[j - zero][k - one]);
                  ret = max(ret, dp[j][k]);
            }
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"10","0001","111001","1","0"};
   Solution ob;
   cout << (ob.findMaxForm(v, 5, 3));
}

입력

["10","0001","111001","1","0"]
5
3

출력

4

프로그램을 실행하면 5개의 0과 3개의 1로 만들 수 있는 문자열의 최대 개수인 4가 출력됩니다. 시간 복잡도는 O(len × m × n)(len은 문자열 배열 길이)로, 각 문자열마다 DP 테이블을 한 번씩 갱신하기 때문입니다.