[백준 9177번] 단어 섞기 (C++)

문제링크 : https://www.acmicpc.net/problem/9177

9177번: 단어 섞기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, dp[201][201]; //각 단어의 길이
string s1, s2, s3;

bool func(int n1, int n2)
{
    if(n1==s1.size() && n2==s2.size()) return 1; //무사 도달
    if(dp[n1][n2]!=-1) return dp[n1][n2]; //시간초과 방지
    if((n1 < s1.size()) && s3[n1+n2]==s1[n1] && func(n1+1, n2)) return dp[n1][n2]=1; //s1에서 가능한 것이 있는가?
    if((n2 < s2.size()) && s3[n1+n2]==s2[n2] && func(n1, n2+1)) return dp[n1][n2]=1; //s2에서 가능한 것이 있는가?
    return dp[n1][n2]=0; //둘 다 불가능
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    for(int i=1; i<=T; i++)
    {
        cin >> s1 >> s2 >> s3;
        memset(dp, -1, sizeof(dp));
        cout << "Data set " << i <<": ";
        cout << (func(0, 0) ? "yes" : "no") <<'\n';
    }

    return 0;
}

 

각 문자열 s1, s2에 대해서 s3의 문자열을 조합하기 위해 가능한 문자가 존재하는지 맨 앞에서부터 확인하며 재귀를 반복한다.

 

각 문자열당 체크해야 할 것은 다음과 같다.

1. 현재 문자열의 위치를 가리키는 인덱스(n1, n2)가 대응하는 문자열의 길이보다 작은가?
2. 각 문자열의 현재 값이 목표 문자열의 문자와 같은가?

위 2가지를 체크후, s1에서 가능한 것이 있었다면 s1 인덱스를 한 칸 증가시키고
s2에서 가능한 것이 있었다면 s2 인덱스를 한 칸 증가시키고 다음 값을 탐색 (재귀)
목표 문자열 s3를 가리키는 값은 n1과 n2를 이용하여 확인 가능
-> s3[n1+n2] == s1[n1] or s2[n2]

만족할때마다 현재 dp[n1][n2]=1로 초기화하고 반환해준다.

둘다 만족못하는 경우는 현재 불가능한 케이스이므로 dp[n1][n2]=0으로 초기화시키고 반환해준다.

 

계속 재귀를 반복하다가 n1이 s1.size()와 같아지고, n2가 s2.size()와 같아지면 무사히 s3의 조합이 끝났다는 것이므로 1을 반환해준다.

그리고 재귀내에 시간초과 방지를 위하여 이미 탐색한 dp 값에 대해서는 바로 반환해주도록 한다.

 

이후 해당 재귀함수를 돌려 나온 값이 1이면 yes를 0이면 no를 출력해주면 된다.