[AtCoder - Panasonic2020 D] String Equivalence

난이도: 1102

 

태그

• Backtracking

 

풀이

1. Normal Form 문자열이 가지는 특징은?

앞에서부터 1글자씩 읽어봅시다.

 

글자를 읽을 때마다, 아래 두 경우 중 하나가 나오게 됩니다.

• 이미 나온 글자인 경우
  앞에서 나온 글자이므로, 앞에서 나왔던 그 글자와 동일해야 합니다.
  이는, 여기의 글자를 다른 걸로 바꾼다면 앞의 글자를 건드리게 되기 때문에,
  앞의 글자부터 읽는 상황일 때는 딱히 건드릴 수가 없죠.
• 새로 나온 글자인 경우
  지금까지 나오지 않은 글자 중 가장 작은 글자여야 합니다.
  // 그렇지 않다면, 그 글자로 바꿔서 더 작은 문자열을 만들 수 있기 때문입니다.

 

즉, 앞에서부터 1글자씩 읽으면서 새로 나오는 글자가 순서대로 a, b, c, d, ...여야 합니다.

반대로, 이러한 문자열은 모두 만들 수 있습니다.

// Normal Form 자체를 만들 수 있으니, 자명히 가능하죠.

 

그러니, "지금까지 나온 글자들"을 들고 다니면서 백트래킹을 돌리면 됩니다.

 

2. 코드

int n;
 
char res[12];
void btk(int idx, char mx){
    if (idx == n){
        for (int i = 0; i < n; i++){ cout << res[i]; }
        cout << endl; return;
    }
    for (char ch = 'a'; ch <= mx; ch++){
        res[idx] = ch; btk(idx+1, mx+(mx==ch));
    }
}
 
void Main(){
    cin >> n; btk(0, 'a');
}