[C++] 백준 12904: A와 B

문제 이해

- 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게 가능한지 알아내는 프로그램

- 연산은 총 두 가지이다.

1. 문자열의 뒤에 A 추가

2. 문자열을 뒤집고, 뒤에 B 추가

 

<입력>

- S (길이: 1 ~ 999)

- T (길이: 2 ~ 1,000)

 

<출력>

- S를 T로 바꿀 수 있다면 1, 없다면 0을 출력하라.

 

 

 

 

문제 풀이

처음에는 역시나 완전 탐색으로 접근해봤다.

백트래킹을 통해 구현했는데, 역시나 시간초과였다.

 

 

이 문제의 정해는 바로 그리디이다.

핵심은 역으로 과정을 진행하는 것이다.

 

 

 

즉 S -> T가 아니라 T -> S를 구하는 것.

이것만 안다면 쉽게 문제를 풀 수 있을 것이다.

 

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin>>s>>t;

    while(s.size() != t.size()){
        if(t.back() == 'A'){
            t.pop_back();
        }else{
            t.pop_back();
            reverse(t.begin(), t.end());
        }
    }

    if(s.compare(t) == 0) cout<<"1";
    else cout<<"0";
    
    return 0;
}

 

 

 

 

배운 점

1. string을 뒤집는 reverse 함수

2. 풀이과정을 역순으로 접근하는 방식