백준 12919번 - A와 B 2(C++)

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

12919번: A와 B 2

 

브루트포스, 재귀로 분류되어있는 문제이다. 

 

문자열을 만들 수 있는 케이스는 두개가 있다. 그렇다면 재귀는 다음과 같이 이루어질 것이다.

 

Recusstion(현재 문자열){
	if(현재 문자열 == 목표 문자열) 함수종료

	Recussiton(A를 더한 문자열)
	Recusstion(B를 더하고 뒤집은 문자열)
}

 

이렇게 해도 답은 도출할 수 있다. 아마도 이 문제를 시키는대로 A -> BA 등 이렇게 s를 b로 만들어가려하면 시간초과가 날 것이다.

 

시간복잡도만 생각하면 만들어야하는 T 문자열의 쵀대 길이가 49이고 S 문자열의 최소 길이는 1이다. 

그렇다면 위 재귀에서 더 만들어질 수 있는 최대 재귀는 2개이고 49번 진행되므로

시간복잡도 = O(2^N) 이다. 그리고 최악의 경우 2^49 이므로 TLE이다.

 

그리고 직관적으로만 봐도 정답 문자열이 BABABB 라고 할 때 S가 A라면 위 코드의 경우 가능성조차 없는 A, AA, AAA 같은 쓸모없는 재귀도 모두 연산해야한다.

 

그래서 여기서 도출해야하는 것은 시작부터 가는것이 아니라 T에서 S를 만들 수 있는가? 로 문제를 바꾸어 풀어야한다. 이 방법은 자주 사용되는 방식이다.

이렇게하면 T가 ABBA라면 두가지 케이스가 가능한 경우, 하나만 가능한 경우로 나눌 수 있어 시간복잡도를 확실히 줄여줄 수 있다. 

 

1. 현재 T의 마지막 문자가 A 라면? 케이스 1번 가능

2. 현재 T의 첫번째 문자가 B 라면? 케이스 2번 가능

 

이대로 T를 계속 재귀적으로 갱신하면 된다. 그러다가 시작 문자열과 같아진다면 전역변수 flag를 두어 모든 재귀가 끝나는 식으로 코드를 작성하였다.

이 경우는 시간복잡도가 정확하지는 않지만 O(log) 라고 생각된다.

 

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

string s, t;
bool flag = false;
void recusstion(string t) {
	if (flag) return;
	if (t == s) {
		flag = true;
		return;
	}

	if (s.size() == t.size()) return;
	
	int len = t.size() - 1;

	string case_1 = t;
	case_1.pop_back();
	string case_2 = t;
	reverse(case_2.begin(), case_2.end());
	case_2.pop_back();
	//cout << case_1 << endl;
	//cout << case_2 << endl;
	if (t[len] == 'A') {
		recusstion(case_1);
		if (t[0] == 'B') {
			recusstion(case_2);
		}
	}
	else{
		if (t[0] == 'B') {
			recusstion(case_2);
		}
		else {
			return;
		}
	}
}

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

	cin >> s >> t;

	recusstion(t);

	if (flag) cout << 1 << '\n';
	else cout << 0 << '\n';
}