[BOJ/백준][Gold4] 9177 : 단어 섞기 (C++)

https://www.acmicpc.net/problem/9177

9177번: 단어 섞기

 

 

[난이도] Gold4
[유형] DP

[풀이]
DP[n][m] : 첫번째 문자열의 문자를 앞에서부터 n개 사용했고, 두번째 문자열의 문자를 앞에서부터 m개 사용했을 때,
           세번째 문자열의 아직 사용하지 않은 문자열을 채울 수 있으면 1, 없으면 0을 return

 

 

#include <string>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int tc,dp[201][201];
string a,b,c;
int sol(int n,int m){
    if(n+m==c.size()) return 1;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    if(n<a.size() && c[n+m]==a[n] && sol(n+1,m)) return ret=1;
    if(m<b.size() && c[n+m]==b[m] && sol(n,m+1)) return ret=1;
    return ret=0;
}
int main(){
    scanf("%d",&tc);
    for(int i=1;i<=tc;i++){
        cin >> a >> b >> c;
        memset(dp,-1,sizeof(dp));
        string ret = sol(0,0) ? "yes":"no";
        cout << "Data set " << i << ": " << ret << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/9177.cpp