백준 12904 A와 B

문제 URL : https://www.acmicpc.net/problem/12904

12904번: A와 B

 

문제접근법 : 

문자열 S와 T를 입력받고 아래 조건에따라 S->T를 만들수 있는지 확인하는문제입니다.

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

문제 글자대로 생각하면 어렵습니다. S->T가 되기위해서 뒤에 A를 추가하거나 뒤집고 B를 추가해서 문자열이 같을때 까지 반복하면 답은 나오겠지만 시간적으로 너무 비효율입니다.

 

그렇다면 반대로 생각하게 된다면 S->T를 만들수 있을때 반대연산을 진행하면 T->S를 만들수 있을것이고,

S->T를 만들수없을땐 T->S도 만들수 없을것입니다.

 

그렇다면 반대연산 조건은 어떻게될까요?

• 문자열의 뒤가 문자열뒤A일경우 A를 제거한다
• 문자열 뒤가 B일경우 문자열뒤 B를제거하고 문자열을 뒤집는다

이런 조건이 되겠죠? 그치만 두 조건이 같은경우가 하나있습니다.

문자열뒤가 A든 B든 처음부터 문자열뒤를 제거한다는건 공통점입니다.

저것을 언제까지 연산을 진행하냐면 S의길이 <T의길이 이기때문에 T의 뒤의 문자열을 제거해거나면 S의 길이가 같아질때까지 확인후 S와 T가 같은지 확인하면 되겠습니다.

 

소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; string s, t; void input() {     cin >> s >> t; } void solve() {     while (s.size() != t.size()) {         char c = t.back();         t.pop_back();         if (c == 'A')continue;         reverse(t.begin(), t.end());     }     cout << (s == t) << "\n"; } int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     input();     solve(); } Colored by Color Scripter

cs

궁금한점 혹은 모르는점 혹은 논리적인 오류등
어떤질문이든 댓글은 언제나 환영입니다.