Baekjoon 9177번 단어 섞기

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

string a, b, c;
int cache[201][201];

int dp(int i, int j, int k){
    // 기저 사례
    if(i == a.size() && j == b.size()) return 1;
    // 메모이제이션
    int& ret = cache[i][j];
    if(ret != -1) return ret;
    // 재귀 호출
    ret = 0;
    if(i < a.size() && a[i] == c[k])
        ret = dp(i+1, j, k+1);
    if(ret) return ret;
    if(j < b.size() && b[j] == c[k])
        ret = dp(i, j+1, k+1);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a >> b >> c;
        memset(cache, -1, sizeof(cache));
        if(dp(0, 0, 0)) cout << "Data set " << i << ": yes\n";
        else cout << "Data set " << i << ": no\n";
    }
    return 0;
}

첫번째 문자열 i 번째, 두번째 문자열의 j 번째 인덱스로 시작해서 세번째 단어를 만들 수 있는지 여부를 dp 배열에 저장해나가는 핵심 아이디어를 보고서도 이해하기가 어려웠던 문제였다.

참고

[9177] 단어 섞기 - How We Coding - 티스토리