백준 8905, 리트

개요

문제 링크
골드 3, 백트래킹
알파벳 소문자를 최대 3자리의 문자로 변형하여 다른 문자열을 구성할 수 있는지 확인하기

---

접근

1. 백트래킹 연습좀 하려고 풀었는데 제한시간 2초에 1932ms으로 통과해버렸다. 당당한 꼴등이 되어보자.
2. 아마 시간이 오래 걸린 이유는 string의 +연산을 그대로 때려박아서 그런 것일텐데, 이해하기 쉬우니 재채점 뜨기 전까지는 냅두려한다.
3. 백트래킹의 핵심은 현재상태, 다음상태, 종료조건, 그리고 가능여부 출력 이라고 했다. 현재상태는 i번째를 바꾸는 상황으로 했다. 다음상태는 i+1이 아니라 i+k번째인데, k개만큼 문자열을 바꿔줄것이기 때문이다. 종료조건은 i = b의 길이 이면서 a == b인 상황으로 했다.
4. 재귀문을 돌려보자. 처음에는 combination으로 길이가 1,2,3인 문자열을 모두 저장했는데 그럴 필요가 없었다. 그냥 b랑 똑같이 바꿔주면 된다. 현재 위치를 바꾸면서 현재 문자의 leet의 길이와 문자열을 저장한다. 그리고 다음단계로 가서, 만약 저장된 leet가 있다면 바꿔주고 다음단계가 가능하다면 1을 출력해주면 된다.
5. 주의할 점은 원 상태로 복귀하는 것, 1부터 k까지 모두 루프를 돌리면서 바꿔줘야 한다는 것이다.

---

Pseudo code

recursive(cur) {
    if (cur == n && a == b) return 1
    if (!a[i] || cur > n) return 0
    if (len[cur])
        a.insert(i, mem[cur])
        if (rec(cur+len[cur]) return 1
    for (j = 1~k)
        len[cur] = j, mem[cur] = b.substr(i,j)
        a.insert(i, mem[cur])
        if (rec(cur+j) return 1
        len[cur] = 0
}

---

Source code

#include <iostream>
#include <string>
using namespace std;

typedef string str;
str a, b, m[26];
int k, n, t[26];

str insert(str a,int i,str x) {
    str b = a.substr(0,i)+x;
    if (i!=a.size()) b += a.substr(i+1);
    return b;
}

bool rec(int i) {
    if (i==n) return a==b;
    if (!a[i]||i>n) return 0;
    char p = a[i]-'a';
    int j = t[p];
    if (j) {
        str c = a;
        str x = m[p];
        a = insert(a,i,x);
        if (rec(i+j)) return 1;
        a = c;
        return 0;
    }
    for (int j=1; j<=k; j++) {
        str c = a;
        str x = b.substr(i,j);
        t[p] = j, m[p] = x;
        a = insert(a,i,x);
        if (rec(i+j)) return 1;
        a = c;
        t[p] = 0;
    }
    return 0;
}

void test() {
    for (int i=0; i<26; i++)
        t[i] = 0;
    cin>>k>>a>>b;
    n = b.size();
    cout<<rec(0)<<"\n";
}

int main() {
    int t;
    cin>>t;
    while(t--) test();
}