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

알고리즘 공부 1주차 - 재귀함수

재귀함수에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천. 

알고리즘 공부 1주차(01): 재귀함수 개념

알고리즘 공부 1주차(01): 재귀함수 개념

백준 12919번  A와 B 2

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

12919번: A와 B 2

문제

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

예제 보려면 더보기 클릭

예제 입력 1

A
BABA

예제 출력 1

1

예제 입력 2

BAAAAABAA
BAABAAAAAB

예제 출력 2

1

예제 입력 3

A
ABBA

예제 출력 3

0

---

문제 설명

처음에는 당연하게도 입력받은 S를 T로 만들 수 있는지에 대해 코드를 짰다. 

문자열 s에 A를 추가하거나 B를 추가해서 뒤집고 다시 함수를 실행하는 것이다. 

따라서 S를 T로 바꾸는 코드는 다음과 같다. 

void st(string s,string t) {
	if (t.compare(s) == 0) {
		cout << 1;
		return;
	}
	if (s.length() == t.length()) return;
	st(s + "A",t);
	string a = s + "B";
	reverse(a.begin(), a.end());
	st(a,t);
	return;
}

그러나 이렇게 코드를 짜면 시간초과에 걸리게 된다.

s가 t가 되는 경우의 수를 하나하나 계산해가며 실행하는 경우 제한시간인 2초를 넘긴다는 것이다. (여기서 문자열 길이의 제한은 1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50 이다.)

최악의 경우 50자의 T를 맞추기 위해 수도없이 코드를 돌리고 뒤집어야 하므로 위 방식으로 코드를 짜선 안된다. 

그럼 어떻게 짜야할까? 다행히 질문게시판에 올라온 글을 통해 힌트를 얻을 수 있었다. 

바로 S에 T를 추가하는 것이 아닌 T에서 삭제해가며 S와 같은지 비교하는 것이다.  

예제 입력 1: S에 "A", T에 "BABA" 입력

1. T의 BABA에서 맨 뒤에 있는 A를 뺀다. T=BAB

2.맨 앞에 있는 B도 빼고 뒤집는다. T=BA 

3.맨 앞에 있는 B를 뺀다. T=A

따라서 S==T 이므로 cout은 1을 출력한다.

(여기서 나는 a라는 bool변수를 만들어 true로 초기값을 세팅한 후 s==t일땐 a=false로 수정하였다. )

앞선 경우의 수를 모두 계산하기 위해 T에서 특정 인덱스를 삭제하거나 뒤집는 것을 반복해야 했는데 만약 T를 그대로 수정한다면 return 되었을때 이미 삭제된 T를 복구할 수 없어 오류가 났다.

따라서 이것을 방지하기 위해 새로운 str이라는 문자열을 만들어 t의 값을 대입해주고, str을 수정해서 다시 재귀함수로 T에 넣는 것을 반복했다.  

추가로 기저조건을 S==T일때 반환하는 것이 아니라 T의 길이와 S의 길이가 같아졌을때 반환하도록 코드를 짜서 쓸데없이 T가 무한루프로 돌지 않도록 했다. 

 

---

제출한 코드(c++)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool a=true;
string str;
void st(string s,string t) {
	if (t.compare(s) == 0) {
		a = false;
	}
	if (s.size() >= t.size()) return;
	if (t[0] == 'B') {
		str = t;
		str.erase(str.begin());
		reverse(str.begin(), str.end());
		st(s, str);
	}
	if (t[t.size() - 1] == 'A') {
		str = t;
		str.erase(str.size()-1);
		st(s, str);
	}
	return; 
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s, t;
	cin >> s >> t;
	st(s, t);
	if (a) cout << 0;
	else
		cout << 1;
}