Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 모음 순열 개수 구하기: 인접 행렬 활용법

문제 개요

숫자 n이 하나 주어졌을 때, 아래 규칙을 모두 만족하는 길이 n의 문자열이 총 몇 개 만들어질 수 있는지 구하는 문제입니다.

  • 모든 문자는 영어 소문자 모음(a, e, i, o, u)이어야 합니다.
  • 모음 'a' 뒤에는 오직 'e'만 올 수 있습니다.
  • 모음 'e' 뒤에는 'a' 또는 'i'만 올 수 있습니다.
  • 모음 'i' 바로 뒤에 또 다른 'i'는 올 수 없습니다.
  • 모음 'o' 뒤에는 'i' 또는 'u'만 올 수 있습니다.
  • 모음 'u' 뒤에는 오직 'a'만 올 수 있습니다.

답이 매우 커질 수 있으므로, 최종 결과는 109 + 7로 나눈 나머지를 구합니다.

예를 들어 입력이 2라면 출력은 10입니다. 조건을 만족하는 모든 문자열은 "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"로 총 10개이기 때문입니다.

접근 방식: 인접 행렬과 행렬 곱셈

이 문제는 그래프 이론의 인접 행렬(adjacency matrix)을 활용하면 깔끔하게 해결할 수 있습니다. 다섯 개의 모음을 정점으로 보고, "한 모음 뒤에 다른 모음이 올 수 있는가"를 행렬의 원소로 표현하는 것입니다.

행렬 A(5×5)는 다음과 같이 정의되며, 행과 열의 순서는 a, e, i, o, u입니다.

A = {
  {0, 1, 0, 0, 0},   // a → e
  {1, 0, 1, 0, 0},   // e → a, i
  {1, 1, 0, 1, 1},   // i → a, e, o, u ('i' 제외)
  {0, 0, 1, 0, 1},   // o → i, u
  {1, 0, 0, 0, 0}    // u → a
}

A[i][j]가 1이라는 것은 모음 i 뒤에 모음 j가 올 수 있다는 의미입니다. 이 행렬을 (n-1)번 거듭제곱한 뒤 모든 원소의 합을 구하면, 길이 n인 유효한 문자열의 총 개수가 됩니다.

알고리즘 단계

  1. 모듈러 값 m := 109 + 7로 설정합니다.
  2. add(a, b): ((a mod m) + (b mod m)) mod m을 반환하는 함수를 정의합니다.
  3. mul(a, b): ((a mod m) × (b mod m)) mod m을 반환하는 함수를 정의합니다.
  4. solve(n): 위에서 정의한 5×5 배열 A를 선언하고, 5×5 크기의 result 배열을 단위 행렬(대각선은 1, 나머지는 0)로 초기화합니다.
  5. n을 1 감소시킨 뒤, i가 1부터 n까지일 동안 result = result × A를 반복 수행합니다.
  6. result의 모든 원소를 더해 sum을 구하고 반환합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9+7;

lli add(lli a, lli b){
    return ((a%m) + (b%m))%m;
}
lli mul(lli a, lli b){
    return ((a%m) * (b%m))%m;
}

class Solution {
public:
    void multiply(lli A[5][5], lli B[5][5]){
        lli C[5][5];
        for(lli i = 0; i < 5; i++){
            for(lli j = 0; j < 5; j++){
                lli temp = 0;
                for(lli k = 0; k < 5; k++){
                    temp = add(temp, mul(A[i][k], B[k][j]));
                }
                C[i][j] = temp;
            }
        }
        for(lli i = 0; i < 5; i++){
            for(lli j = 0; j < 5; j++){
                A[i][j] = C[i][j];
            }
        }
    }

    lli solve(lli n){
        lli A[5][5] = { { 0, 1, 0, 0, 0 }, { 1, 0, 1, 0, 0 },
                        { 1, 1, 0, 1, 1 }, { 0, 0, 1, 0, 1 },
                        { 1, 0, 0, 0, 0 } };
        lli result[5][5];
        // 단위 행렬로 초기화
        for (lli i = 0; i < 5; i++) {
            for (lli j = 0; j < 5; j++) {
                if (i == j)
                    result[i][j] = 1;
                else
                    result[i][j] = 0;
            }
        }
        n--;
        for (lli i = 1; i <= n; i++)
            multiply(result, A);
        lli sum = 0;
        for (lli i = 0; i < 5; i++) {
            for (lli j = 0; j < 5; j++) {
                sum = add(result[i][j], sum);
            }
        }
        return sum;
    }

    int countVowelPermutation(int n) {
        return solve(n);
    }
};

int main(){
    Solution ob;
    cout << (ob.countVowelPermutation(2));
}

입력

2

출력

10

복잡도 및 최적화 팁

위 구현은 행렬 곱셈을 n-1번 반복하므로 시간 복잡도는 O(n × 5³)입니다. n이 매우 클 경우에는 분할 정복 기반의 빠른 거듭제곱(fast exponentiation)을 적용하면 O(5³ log n)으로 줄일 수 있습니다. 또한 DP 방식으로도 해결할 수 있는데, dp[v]를 "현재 문자열의 마지막 문자가 v인 경우의 수"로 정의하고 각 단계마다 전이 규칙에 따라 값을 갱신하면 O(n) 시간 안에 답을 구할 수 있습니다.