C++에서 길이 L인 문자열의 매직 쌍 개수 구하기

문제 개요

두 문자열 str1과 str2가 주어졌을 때, 길이가 L인 매직 쌍(magical pair)의 개수를 구하는 문제입니다. 모든 인덱스 i에 대해 str1[i] < str2[i]를 만족할 때 두 문자열은 매직 관계에 있다고 정의합니다. 쌍의 개수는 문자열 길이가 길어질수록 기하급수적으로 커지기 때문에, 최종 답은 10⁹(1,000,000,000)으로 나눈 나머지로 반환해야 합니다. 문자열에는 소문자 알파벳만 포함된다고 가정합니다.

풀이 접근 방법

핵심 아이디어는 간단한 수학적 규칙을 찾는 것입니다. 먼저 길이 L = 1인 경우를 살펴보겠습니다. str1의 첫 번째 문자가 'a'라면, str2의 같은 위치에는 'b'부터 'z'까지 총 25가지 문자가 올 수 있습니다. str1이 'b'라면 24가지, 'c'라면 23가지처럼 점점 줄어들므로, 한 자리에서 가능한 전체 조합은 다음과 같습니다.

25 + 24 + 23 + ... + 1 = 325

길이가 2라면 각 자리마다 독립적으로 325가지 조합이 성립하므로 325² = 105,625가 되고, 일반화하면 길이 L인 문자열의 매직 쌍 개수는 325^L입니다. L이 커지면 값이 매우 빠르게 증가하기 때문에, 거듭제곱을 계산하는 과정에서 10⁹으로 나눈 나머지를 취하는 모듈러 거듭제곱(modular exponentiation) 기법을 사용합니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;
int power(int a, unsigned int b, int mod) {
    int res = 1;
    a = a % mod;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % mod;
        b = b >> 1;
        a = (a * a) % mod;
    }
    return res;
}
int main() {
    int L = 2, P = pow(10, 9);
    int res = power(325, L, P);
    cout << "Combinations: " << res << endl;
}

실행 결과

Combinations: 105625

L = 2일 때 325² = 105,625가 정확히 출력되는 것을 확인할 수 있습니다. 위 알고리즘은 거듭제곱을 이진 분할 방식으로 계산하므로 시간 복잡도가 O(log L)로 매우 효율적이며, L이 큰 경우에도 빠르게 답을 구할 수 있습니다.