[BOJ] 12904번 | A와 B (C++)

🔗문제 보러가기

12904번: A와 B

 

👨‍💻풀이 과정

 

그리디 방식으로도 풀 수 있다고 하길래, 어떻게 하는지 궁금해서 관련 🔗힌트 글을 찾아봤습니다. 이런 생각을 할 수 있다니... 대단하네요. 세상에는 천재가 너무 많습니다.

 

기존 문자열인 S에서 목표로 하는 문자열 T로 변환하는 경우의 수는 너무 많은데 비해, 그 경우의 수가 다 올바른 길도 아닙니다. 그렇기에, T에서 S로 반대로 변환하는 것이 아이디어더군요. T에서 S로 변환해 나가는 과정은 S에서 T로 변환할 때의 올바른 과정만이 담겨 있을 테니까요.

 

다음 방식에 따라 T를 S로 변환할 수 있으면 True, T의 길이가 1 이하가 됐는데도 S가 안 된다면 False를 반환해주면 되겠습니다.

 

1. 문자열 T의 마지막 문자가 A인 경우
   • 1번 연산인 "문자열의 뒤에 A를 추가한다"만 가능
   • 반대로 역추적해 나가는 과정이므로, T의 마지막 문자인 A를 제거하고 다시 검사
2. 문자열 T의 마지막 문자가 B인 경우
   • 2번 연산인 "문자열을 뒤집고, 뒤에 B를 추가한다"만 가능
   • 반대로 역추적해 나가는 과정이므로, T의 마지막 문자인 B를 제거하고, T를 뒤집은 다음에 다시 검사

 

✏️ 소스 코드 및 결과

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

bool IsAvailable(const string& source, string currentString)
{
    if (source == currentString)        return true;
    if (currentString.length() <= 1)    return false;

    if (currentString.back() == 'A')
    {
        currentString.pop_back();
        return IsAvailable(source, currentString);
    }

    currentString.pop_back();
    reverse(currentString.begin(), currentString.end());
    return IsAvailable(source, currentString);
}

int main()
{
    FAST_IO
    string source, destination;
    cin >> source >> destination;

    cout << IsAvailable(source, destination);
    return 0;
}