[DP] 와일드카드(WILDCARD) 알고스팟 (동적계획법)

문제 출처 - 알고스팟

 우리가 익히 잘 알고있는 와일드카드(*)문자는 탐색기에서 검색을 하는 등에 많이 사용되죠. 이 문제는 주어진 패턴이있을 때 패턴과 일치하는 문자열을 찾아서 알파벳 순서대로 출력하는 겁니다. (알파벳 순으로 안해서 오답이 났었네요)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <iostream> #include <string> #include <vector> #include <algorithm> #include <string.h> using namespace std; // 동적 계획법으로 풀기 // // -1은 아직 답이 계산되지 않았음을 의미한다. // 1은 해당 입력들이 서로 대응됨을 의미한다. // 0은 해당 입력들이 서로 대응되지 않음을 의미한다. int cache[101][101]; //패턴과 문자열 string W, S; //와일드카드 패턴 W[w..]가 문자열 S[s..]에 대응되는지 여부를 반환한다. bool matchMemoized(int w, int s) {        //메모이제이션        int& ret = cache[w][s];        if (ret != -1) return ret; // 이미 계산한 거라면 반환한다.        //W[w]와 S[s]를 맞춰나간다.        while (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s])) {               ++w;               ++s;        }        //더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.        // 2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 참이다.        if (w == W.size()) return ret = (s == S.size());        if (W[w] == '*')               for (int skip = 0; skip + s <= S.size(); ++skip)                      if (matchMemoized(w + 1, s + skip))                            return ret = 1;        // 3. 이 외의 경우에는 모두 대응되지 않는다.        return ret = 0; } vector<string> answers; int main() {        int c;        cin >> c;        for (int i = 0; i < c; ++i) {               cin >> W;               int n;               cin >> n;               for (int j = 0; j < n; ++j) {                      cin >> S;                      memset(cache, -1, sizeof(int) * 101 * 101);                      if (matchMemoized(0, 0) == 1)                            answers.push_back(S);                                     }               sort(answers.begin(), answers.end(), [](string&a, string&b) { return a < b; });               //reverse(answers.begin(), answers.end())               for (int k = 0; k < answers.size(); ++k) {                      cout << answers[k] << endl;               }               answers.clear();        }        //cin >> c;        return 0; } Colored by Color Scripter

cs

추가적으로 sort에 비교함수로 람다를 쓸 수도 있다는 것을 알게되었습니다. dp문제는 이 문제가 처음이라서 더 많이 풀어봐야 감을 익힐 수 있을 것 같습니다! 메모이제이션은 정말 멋진 방법인 것 같아요.