8676. 동현이와 한결이는 아이돌

문제(요약)

부분문자열의 갯수를 구하시오. (출처)

접근법

완전탐색구현 후, 시간초과 발생하여 Dynamic Programing (Memoization) 적용

풀이

#include <iostream>
#include <vector>

using namespace std;

string S;
string sT = "SAMSUNG";
const int NUM = 1000000007;

vector <vector<int>> memo;


int fnSolve(int IdxT, int IdxS) {

    if (sT.size() == IdxT) {
        return 1;
    }

    if (S.size() == IdxS) {
        return 0;
    }

    int Ret = memo[IdxT][IdxS];
    if (Ret != -1) {
        return Ret;
    }

    if (sT[IdxT] == S[IdxS]) {
        memo[IdxT][IdxS] = (fnSolve(IdxT, IdxS+1)%NUM + fnSolve(IdxT+1, IdxS)%NUM)%NUM;
        return memo[IdxT][IdxS];
    }
    else {
        return fnSolve(IdxT, IdxS+1) % NUM;
    }

}

int main() {
    int T;
    cin >> T;
    for (int t=1;t<=T;t++) {

        cin >> S;

        memo = vector<vector<int>>(sT.size(), vector<int>(S.size(), -1));

        cout << "#" << t << " " << fnSolve(0, 0) << endl;
    }
    return 0;
}