boj 9177 단어 섞기

www.acmicpc.net/problem/9177

9177번: 단어 섞기

str1 : 첫 번째 단어

str2 : 두 번째 단어

result : 세 번째 단어

 

dp[idx1][idx2] : 현재 확인하려는 알파벳이 str1[idx1], str2[idx2]일 때 result를 만들 수 있는지 여부

 

재귀를 통해 두 단어와 세 번째 단어를 비교할 인덱스(idx1, idx2, idx)를 넘겨줍니다.

str1[idx1] == result[idx]이면 첫 번째 단어와 세 번째 단어의 인덱스를 1 증가(idx1 + 1, idx2, idx + 1)

str2[idx2] == result[idx]이면 두 번째 단어와 세 번째 단어의 인덱스를 1 증가(idx1, idx2 + 1, idx + 1)

를 확인해줍니다.

 

인덱스의 조합이 중복으로 나오기때문에 시간적 손해를 줄이기위해 dp를 사용하였습니다.

 

 

#include <iostream>
#include <string>
#include <cstring>
#define max(a, b) {a > b ? a : b}
using namespace std;
 
string str1, str2, result;
int dp[201][201];
int size1, size2, rsize;
 
int func(int idx1, int idx2, int idx) {
    if (idx == rsize) return 1;
 
    int &ret = dp[idx1][idx2];
 
    if (ret != -1) return ret;
    ret = 0;
 
    if (idx1 < size1 && str1[idx1] == result[idx]) ret = func(idx1 + 1, idx2, idx + 1);
    if (idx2 < size2 && str2[idx2] == result[idx]) ret = max(ret, func(idx1, idx2 + 1, idx + 1));
 
    return ret;
}
 
void input() {
    cin >> str1 >> str2 >> result;
    size1 = str1.size();
    size2 = str2.size();
    rsize = result.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        memset(dp, -1, sizeof(dp));
        cout << "Data set " << t << ": ";
        input();
        if (func(0, 0, 0)) cout << "yes\n";
        else cout << "no\n";
    }
 
 
    return 0;
}