[백준/c++] 12919번: A와 B 2

 

 

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

12919번: A와 B 2

 

문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임.

- 문자열 뒤에 A 추가

- 문자열 뒤에 B 추가하고 뒤집기

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

바꿀 수 있으면 1, 없으면 0 출력

 

이런 문제는 뒤집어서 생각해볼 필요도 있다.

처음엔 재귀로 모든 경우를 구했더니 시간 초과가 발생했다ㅜ

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

string tmp = "";
bool flag = false;

void Game(string s, string t){
    if(s == t){
        cout << 1 << '\n';
        flag = true;
        return;
    }
    
    if(s.size() >= t.size()) return; //무조건 0 - 잘못된 입력
    
    if(t[t.size()-1] == 'A'){
        tmp = t;
        tmp.erase(tmp.size() - 1);
        Game(s, tmp);
    }
    if(t[0] == 'B'){
        tmp = t;
        tmp.erase(tmp.begin());
        reverse(tmp.begin(), tmp.end());
        Game(s, tmp);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s, t;
    cin >> s >> t;
    Game(s, t);
    if(!flag) cout << 0 << '\n';
    return 0;
}

 

S에서 T로 만드는 게 아니라 T를 줄이면서 S로 만들어버리는 것이다!

A는 뒤에 붙이는 것이므로 이 경우엔 맨 뒤를 erase

B는 뒤에 붙여서 뒤집으니까 맨 앞에 있을 것이다. 맨 앞을 erase 하고 뒤집어준다.

 

 

 

오랜만에 코테문제를 푸니까 하나도 모르겠다...

큰일이네ㅠ