[백준 12904] A와 B
그리디 알고리즘과 문자열이 결합되어 나온 문제입니다.
Key Point
본 문제에서 주목할만한 점은 다음과 같습니다.
- T에서 S로 거꾸로 돌아가는 것을 생각해봅시다.
S에서 T로 가는 방법을 생각해보는 것은 시간을 충분히 들이면 물론 할 수는 있겠지만
보통 before, after가 주어진 경우에는 거꾸로 생각해보는 것이 더 편할 수 있습니다.
해석
문제에서 언급된 문자열 연산은 다음과 같습니다.
- 문자열의 뒤에 A를 추가한다.
- 문자열을 뒤집고 뒤에 B를 추가한다.
이를 거꾸로 생각하면 다음과 같습니다.
- 문자열의 뒤에 A를 추가한다.
문자열의 맨 뒷글자가 A이면, 맨 뒷글자 A를 제거한다. - 문자열을 뒤집고 뒤에 B를 추가한다.
문자열을 뒤집은 후 맨 앞글자 B를 제거한다.
정리
T에서 S로 거꾸로 돌아갈 때 기준을 하나 잡아야 합니다.
맨 뒷글자가 A라면, 1번 연산을 수행한 후의 결과라는 것을 의미하므로 A를 제거합니다.
맨 뒷글자가 B라면, 문자열을 뒤집은 후 맨 앞글자 B를 제거하면 됩니다.
위 과정을 반복하면 반드시 문자열의 길이가 1 작아지기 때문에
문자열 S의 길이와 같아질 때까지만 수행하면 됩니다.
만약, S의 길이와 같아졌는데도 두 문자열이 서로 다르다면 만들 수 없다는 것을 의미하므로 0을,
같아졌다면 문제의 요구사항대로 1을 출력하면 답이 됩니다.
문제 : 백준 12904 - A와 B