백준 12904: A와 B

A와 B 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

5835

2689

2250

46.211%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

B
ABBA

예제 출력 1 복사

1

예제 입력 2 복사

AB
ABB

예제 출력 2 복사

0

출처

• 문제의 오타를 찾은 사람: apjw6112
• 문제를 번역한 사람: baekjoon

처음에는 dfs로 코드를 구성했다.

시간초과 코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;
string s, t;
bool answer = false; 

void condition1() {//문자열 뒤집고 B 추가
string temp = s;
s.clear();
int size= temp.size();
for (int i = size-1; i >= 0; i--) {
s += temp[i];//뒤에서부터 하나씩 넣어주고
}
s += 'B';

}
void condition2() {//문자열 맨 뒤에 A 추가
s += 'A';
}

void dfs(int s_size, int t_size) {
if (s.size() == t.size()) {
//같아지면 같은지 확인해보고 answer = 1;
if (s==t) 
answer = true;
return;
}

string temp;//dfs에서 처음 받는 문자열에다가 우선s를 담아주고 
temp = s;//빈 배열에 저장해뒀다가 나중에 dfs가 종료되고 다시 돌아올때 다시 s에 저장해뒀던 걸 넣는다.

condition1(), dfs(s_size + 1, t_size), s = temp;
condition2(), dfs(s_size + 1, t_size), s = temp;

}

int main()
{
cin >> s >> t;
int a = s.size();
int b = t.size();
dfs(a, b);
if (answer)cout << 1;
else
cout << 0; 
return 0;
}

근데 시간초과가 나서 결국 실패 ㅠ

그래서 

인터넷을 좀 뒤져봤는데, 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string s, t;
bool answer = false; 

int main()
{
cin >> s >> t;
while (1) {

if (s.size() == t.size()) {
if (s == t)
answer= 1;
break;
}

if (t[t.size() - 1] == 'A')
t.pop_back();
else {
t.pop_back();
reverse(t.begin(), t.end());
}
}
if (answer)cout << 1;
else
cout << 0; 
return 0;
}

S에서 T로 접근하는 것이 아니라, T에서 S로 접근하는 방식으로 풀어주면 된다는 것을 발견했다.

맨 뒷글자가 A면 그냥 A를 날려버리고 B면 맨 B를 날리고  뒤집어주면 된다. 

나름 대단한 해결책인 인듯하다

ex

S-> B

T-> ABBA

 

T= ABB

T= BA

T= B

S= B