[BAEKJOON] 12919번 A와 B 2

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

12919번: A와 B 2

 

문제조건

1. A,B로만 이루어진 두 문자열 S, T 가 주어지고, S를 T로 바꾼다.
2. 문자열뒤에 A를 추가한다.
3. 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.
4. S를 T로 바꿀수 있으면 1 출력, 아니면 0 출력

 

S에서 두가지 행동만 할 수 있는데 행동들이 전부 문자 길이를 늘리는 것이므로 S, T가 똑같은 길이가 되었을때, 같은 문자열이 아니라면 0을 출력하면된다.

모든 경우의 수를 구해서 S와 T가 같아지는 것만 판단하면 되므로, 완전탐색으로 DFS를 생각해서 풀었다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string s, t;
bool judge;

void dfs(string s) {
	if (s.length() == t.length()) {
		if (s == t) judge = true;
		return;
	}
	dfs(s + 'A');
	string res = s;
	reverse(res.begin(), res.end());
	dfs('B' + res);
}

int main(){
	cin >> s >> t;
	dfs(s);
	if (judge) cout << 1;
	else cout << 0;
}

????????????????

 

처참하다,,,,

왜 시간초과가 나나 생각해보니,, S → T 의 과정은 최대 2^50의 시간복잡도로 엄청 큰 반면, 역으로 생각해서 T → S 의 과정은 조건이 만족할 경우만 DFS 탐색을 하므로 복잡도가 많이 줄여진다,,!

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string s, t;
bool judge;

void dfs(string t) {
	if (s.length() == t.length()) {
		if (s == t) judge = true;
		return;
	}
	if (t[t.length() - 1] == 'A') {
		t.pop_back();
		dfs(t);
		t.push_back('A');
	}
	if (t[0] == 'B') {
		reverse(t.begin(), t.end());
		t.pop_back();
		dfs(t);
	}
}

int main(){
	cin >> s >> t;
	dfs(t);
	if (judge) cout << 1;
	else cout << 0;
}

달다^^

완전탐색 문제를 풀때, 발상의 전환으로 반대로도 생각하자. 시간복잡도 중요!!