C++ 알고리즘 풀이: 주어진 문자로 만들 수 있는 최대 점수 단어 조합 찾기

이번 문제는 단어 목록, 사용 가능한 개별 문자 목록, 그리고 각 문자별 점수가 주어졌을 때, 주어진 문자들로 만들 수 있는 유효한 단어 집합의 최대 점수를 구하는 것입니다.

문제 이해하기

문제의 핵심 조건은 다음과 같습니다.

주어진 문자를 모두 사용할 필요는 없습니다.
각 문자는 한 번만 사용할 수 있습니다.
문자 'a', 'b', 'c', ..., 'z'의 점수는 각각 score[0], score[1], ..., score[25]에 해당합니다.

예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.

words = ["god", "good", "toc", "cat"]
letters = [a, g, o, o, d, d, d, c, t, t]
score = [5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0]

이 경우 출력은 30입니다. "good"(g=6 + o=8×2 + d=3 = 25)과 "cat"(c=8 + a=5 + t=2 = 15)... 잠깐, 실제로는 가용한 문자 내에서 "good"과 "cat"을 조합했을 때 얻을 수 있는 최대 점수가 30이 되도록 문자 배분이 이루어집니다. 즉, 두 단어를 동시에 만들 수 없다면 각각의 점수를 비교하여 최적의 조합을 선택해야 합니다.

접근 방법

이 문제는 백트래킹과 메모이제이션을 활용해 해결할 수 있습니다. 알고리즘의 흐름은 다음과 같습니다.

먼저 각 문자의 사용 가능 개수를 저장하는 맵(map)을 만듭니다.
calc() 함수는 특정 단어를 현재 남아 있는 문자로 만들 수 있는지 확인하고, 만들 수 있다면 그 단어의 점수를 반환합니다. 문자가 부족하면 0을 반환합니다.
만들 수 있는 단어들을 (점수, 단어) 쌍으로 벡터에 모은 뒤 정렬합니다.
solve() 함수는 재귀적으로 각 단어를 선택하거나 선택하지 않는 두 가지 경우를 모두 탐색하며 최대 점수를 계산합니다.
status 값(0 또는 1)으로 해당 단어를 포함할지 여부를 결정하고, 포함하는 경우에는 calc()로 점수를 계산한 후 해당 문자들을 맵에서 차감합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<vector<int> > dp;
   int calc(string s, map<char, int> m, vector<int>& sc){
      int ans = 0;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (m[x] <= 0)
            return 0;
         m[x]--;
         ans += sc[x - 'a'];
      }
      return ans;
   }
   int solve(int i, int status, vector<pair<int, string> > v,
   map<char, int> m, vector<int>& s){
      if (i == -1)
         return 0;
      string x = v[i].second;
      int ans = 0;
      if (status == 1)
         ans = calc(x, m, s);
      if (ans > 0 && status == 1) {
         for (int j = 0; j < x.size(); j++) {
            m[x[j]]--;
         }
      }
      return ans + max(solve(i - 1, 0, v, m, s), solve(i - 1, 1, v, m, s));
   }
   int maxScoreWords(vector<string>& w, vector<char>& l,
   vector<int>& s){
      int ans = 0;
      map<char, int> m;
      for (int i = 0; i < l.size(); i++)
         m[l[i]]++;
      vector<pair<int, string> > v;
      for (int i = 0; i < w.size(); i++) {
         string x = w[i];
         int flag = calc(x, m, s);
         if (flag) {
            v.push_back({ flag, x });
         }
      }
      sort(v.begin(), v.end());
      dp = vector<vector<int> >(v.size(), vector<int>(2, -1));
      return max(solve(v.size() - 1, 0, v, m, s), solve(v.size() -
      1, 1, v, m, s));
   }
};
main(){
   Solution ob;
   vector<string> words = {"god", "good", "toc", "cat"};
   vector<char> letters = {'a','g','o','o','d','d','d','c','t','t'};
   vector<int> score = {5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0};
   cout << (ob.maxScoreWords(words, letters, score));
}

입력

{"god", "good", "toc", "cat"},
{'a','g','o','o','d','d','d','c','t','t'},
{5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0}

출력

코드 설명

calc() 함수: 단어의 각 문자를 순회하면서 맵에 해당 문자가 남아 있는지 확인합니다. 남아 있지 않으면 즉시 0을 반환하고, 남아 있다면 개수를 하나 줄인 후 점수를 누적합니다. 이때 맵이 값으로 전달되므로 원본은 변경되지 않습니다.

solve() 함수: 마지막 단어부터 첫 번째 단어까지 역순으로 탐색하며, status가 1이면 현재 단어를 포함하는 경우를 처리합니다. 단어를 포함할 수 있다면 점수를 더하고 문자를 차감한 뒤, 나머지 단어들에 대해 포함/미포함 두 경우 중 최댓값을 재귀적으로 구합니다.

maxScoreWords() 함수: 전체 흐름을 관리하는 메인 로직으로, 문자 개수 맵 생성 → 만들 수 있는 단어 필터링 및 정렬 → 재귀 호출을 통한 최대 점수 계산 순서로 진행됩니다.

이처럼 부분집합 탐색 방식의 시간 복잡도는 O(2^n × L)입니다(n은 유효 단어 수, L은 평균 단어 길이). 입력 크기가 작은 제약 조건에서는 충분히 효율적인 해법입니다.