문제(요약)
부분문자열의 갯수를 구하시오. (출처)
접근법
완전탐색구현 후, 시간초과 발생하여 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;
}
'알고리즘 트레이닝 > SW Expert Academy' 카테고리의 다른 글
9940. 순열1 (0) | 2020.05.14 |
---|---|
9839. 최고의 쌍 (0) | 2020.05.02 |
8821. 적고 지우기 (0) | 2019.11.01 |
8658. Summation (0) | 2019.10.09 |
1206. [S/W 문제해결 기본] 1일차 - View (0) | 2019.09.16 |