[BOJ 9177] 단어 섞기

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

9177번: 단어 섞기

 

- 문제 요약

 

첫 번째 줄에 데이터 집합의 개수 N이 입력된다. (1 <=N <=1000)

두 번째 줄부터 N개의 줄에는 각 줄마다 단어 3개가 입력된다.

첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있으면 yes, 아니면 no를 출력하자.

단, 세 번째 단어를 만들 때 첫 번째 단어와 두 번째 단어의 원래 순서가 섞이면 안 된다.

(입출력 형식은 아래를 참고하자)

입출력 형식

 

 

- 알고리즘 정리

 

기본적인 DP 점화식을 세워서 풀 수 있는 문제입니다.

식은 아래와 같습니다.

dp[i][j] : 세 번째 문자열을 만들 때, 첫 번째 문자열의 1~i번 문자와 두 번째 문자열의 1~j번 문자를 사용한 경우 세 번째 문자열에서 아직 사용하지 않은 문자열을 채울 수 있는 경우 1, 아니면 0을 리턴

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 201
int n,dp[MAX][MAX];
string a,b,c;

bool f(int aa,int bb){
	if(aa+bb==c.size()){
		return true;
	}
	int &ret=dp[aa][bb];
	if(ret!=-1){
		return ret;
	}
    if(aa<a.size()&&c[aa+bb]==a[aa]&&f(aa+1,bb)){
    	return ret=1;
	}
	if(bb<b.size()&&c[aa+bb]==b[bb]&&f(aa,bb+1)){
		return ret=1;
	}
    return ret=0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a>>b>>c;
		memset(dp,-1,sizeof(dp));
		string result=f(0,0)?"yes":"no";
		cout<<"Data set "<<i+1<<": "<<result<<'\n';
	}
}

코드 제출 결과