[백준 12904] A와 B (C#, C++) - soo:bak

문제 링크

12904번 - A와 B

설명

문자열 S에 두 가지 연산을 사용할 수 있는 상황에서 S와 T (

S

<

T

≤ 1000)가 주어질 때, S를 T로 만들 수 있는지 판별하는 문제입니다.

사용 가능한 연산:

1. 문자열 뒤에 A를 추가
2. 문자열을 뒤집은 후 뒤에 B를 추가

접근법

S에서 시작하여 T를 만드는 정방향 탐색은 각 단계에서 두 가지 선택이 가능하므로 경우의 수가 지수적으로 증가합니다.

하지만 T에서 시작하여 S로 줄이는 역방향 접근은 각 단계에서 선택이 유일하게 결정되므로 효율적입니다.

역연산의 규칙은 다음과 같습니다:

• 마지막 문자가 A인 경우: A를 제거 (연산 1의 역)
• 마지막 문자가 B인 경우: B를 제거한 후 문자열을 뒤집기 (연산 2의 역)

T의 길이가 S의 길이와 같아질 때까지 위 규칙을 반복 적용합니다.

최종적으로 얻은 문자열이 S와 일치하면 1을, 다르면 0을 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var s = Console.ReadLine()!;
      var t = Console.ReadLine()!;

      var chars = new List<char>(t);

      while (chars.Count > s.Length) {
        var last = chars[^1];
        chars.RemoveAt(chars.Count - 1);
        if (last == 'B') chars.Reverse();
      }

      var result = new string(chars.ToArray());

      Console.WriteLine(result == s ? 1 : 0);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

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

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

  while (t.size() > s.size()) {
    char last = t.back();
    t.pop_back();
    if (last == 'B') reverse(t.begin(), t.end());
  }

  cout << (t == s ? 1 : 0) << "\n";

  return 0;
}