백준 12919번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	골드 5

---

풀이

 밀린 문제 정리다. 이 문제도 역발상이 중요한 문제이다. S->T로 가는 것이 어렵다면, 그 역방향으로도 갈 수 있는지 생각하는 유연함이 필요하다. 저번 16953번(https://codejin.tistory.com/268)에서도 반대 방향으로 역추적하는 방식을 사용하는 풀이를 보이기도 했었다. 이런 발상을 바로 할 수 있도록 연습을 더 해야겠다.

 

 이 문제는 어떻게 역추적을 하는지 생각해보자. 문제에서 말하는 연산을 위에서부터 각각 a, b연산이라고 간단하게 부르기로 하자. S->T로 가기 위해서는 a작업을 할수도 있고, b작업을 할 수도 있다. 당연히 모든 경우의 수를 따질수는 있겠으나, 이 경우 O(2^(T길이-S길이))가 된다. S의 길이가 1, T의 길이 50같은 극한 케이스는 얼마든지 존재할테니(없더라도 있다고 가정하는 것이 연습에 좋으니) 당연히 불가능할 것이다. 그렇다고 어떤 작업을 선택하는 것이 효율적인지는 선택하기 어렵다. S에 적당히 a, b연산을 한 문자열을 S'라고 하면, S'가 T의 부분 문자열일수도 있고, S'를 뒤집은 것이 부분문자열일수도 있다. 또한 여러 곳에서 나올 수도 있으며, 어디에서 어떤 작업을 다시 선택하는지 생각해보면 너무 복잡한 문제가 된다.

 

하지만 S에서 T를 만들었다면, 작업을 거꾸로 하면서 S로 돌아갈수도 있다. 이제부터 a작업을 문자열 뒤의 A를 제거하는 작업, b작업을 문자열을 뒤집은 후 B를 지우는 작업으로 바꿔 생각해보자. T에서 S로 가기 위해 문자를 지워볼 것이다. 우리가 선택할 방법은 명확하다. 문자열의 맨 뒤 문자가 A라면 지워본 후, 남은 문자열에 대해 다시 탐색한다. 또한, 문자열의 맨 앞의 글자가 B라면 문자열을 뒤집고, 맨 뒤로 온 B를 지운 후 남은 문자열을 탐색한다. 이런 방식으로 S와 T의 길이가 같아졌다면 두 문자열이 같은지 검사한다. 해당 방식은 S로 T를 만드려는 것보다 확실히 쉬울 것이다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

string s, rs, t;

void input() {
	cin >> s >> t;
	rs = s;
	reverse(ALL(rs));
}

bool is_substr(string target) {
	if (target.find(s) != string::npos ||
		target.find(rs) != string::npos) return true;
	return false;
}

int back_tracking(string target) {
    if (target.length() == s.length()) {
		return s == target;
	}
	if (!is_substr(target)) {
		return 0;
	}

	int res = 0;
	if (*target.rbegin() == 'A') {
		res |= back_tracking(target.substr(0, target.length() - 1));
	}
	if (*target.begin() == 'B') {
		string tmp = target.substr(1, target.length());
		reverse(tmp.begin(), tmp.end());
		res |= back_tracking(tmp);
	}
	return res;
}

void sol() {
	cout << back_tracking(t);
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}

 

코드에 백트래킹이라고 적어놓긴 했는데, 풀이를 보면 백트래킹은 아닌거 같다. 저때 당시의 나는 왜 함수명을 백트래킹으로 적었는지 잘 모르겠다.