C++로 인코딩된 메시지를 디코딩하는 방법의 수 구하기

정수들로 이루어진 문자열 형태의 인코딩된 메시지가 주어졌다고 가정해 보겠습니다. 각 숫자는 알파벳의 특정 글자에 매핑됩니다. 즉, a는 1, b는 2, c는 3에 대응되는 식입니다. 여기에 더해, 메시지에는 '*' 문자가 포함될 수 있는데, 이 문자는 1부터 9까지의 어느 숫자로도 매핑될 수 있습니다. 따라서 메시지 'input'이 주어졌을 때, 이를 디코딩할 수 있는 서로 다른 방법이 총 몇 가지인지 구해야 합니다.

예를 들어 입력이 input = "18"이라면 출력은 2가 됩니다.

이 메시지는 두 가지 방식으로 디코딩할 수 있습니다. 첫째, 1은 "a"에, 8은 "h"에 대응하므로 "ah"가 되고, 둘째, 18 전체가 "r"에 대응하므로 "r"이 됩니다. 따라서 총 2가지 방법으로 디코딩이 가능합니다.

문제 해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 위치에서 한 자리 숫자로 디코딩하는 경우와 두 자리 숫자(10~26)로 디코딩하는 경우를 나누어 누적해 나가며, '*' 문자가 등장할 때는 가능한 모든 숫자 조합을 함께 고려합니다. 구체적인 절차는 다음과 같습니다 −

n := 입력 문자열의 길이
크기가 n+1인 배열 dynArr를 선언하고 0으로 초기화
p := 1 (디코딩 가능 여부를 나타내는 플래그)
k := '0' (이전 문자를 저장하는 변수)
dynArr[0] := 1
i := 1부터 n까지 1씩 증가시키며 반복 −
- c := input[i - 1]
- c가 '0'이면서 k가 '1', '2', '*' 중 어느 것도 아니라면 −
  - p := 0
  - 반복문 탈출
- input[i - 1]이 '*'라면 −
  - dynArr[i] := (dynArr[i - 1] * 9) mod m ('*'는 1~9의 아홉 가지 값을 가질 수 있음)
  - k가 '1' 또는 '*'라면 − dynArr[i] := (dynArr[i] + dynArr[i - 2] * 9) mod m
  - k가 '2' 또는 '*'라면 − dynArr[i] := (dynArr[i] + (dynArr[i - 2] * 6) mod m) mod m
- 그 외의 경우 −
  - c가 '0'이 아니라면 dynArr[i] := dynArr[i - 1]
  - k가 '1' 또는 '*'라면 − dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
  - (k가 '2' 또는 '*')이고 input[i - 1] <= '6'이라면 − dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
- k := c
p가 0이 아니면 dynArr[n]을 반환하고, 그렇지 않으면 0을 반환

여기서 상수 m(10^9 + 7)은 결과값이 지나치게 커지는 것을 방지하기 위해 사용하는 모듈로 값입니다.

예제

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다 −

#include<bits/stdc++.h>

using namespace std;

const long m = 1e9 + 7;

int solve(string input) {
   int n = input.length();
   long long dynArr[n + 1] = {0};

   bool p = 1;
   char k = '0';

   dynArr[0] = 1;
   for (int i = 1; i <= n; i++) {
      char c = input[i - 1];
      if (c == 0 && !(k == '1' || k == '2' || k == '*')) {
         p = 0;
         break;
      }
      if (input[i - 1] == '*') {
         dynArr[i] = (dynArr[i - 1] * 9) % m;
         if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2] * 9) % m;
         if (k == '2' || k == '*') dynArr[i] = (dynArr[i] + (dynArr[i - 2] * 6) % m) % m;
      } else {
         if (c != '0') dynArr[i] = dynArr[i - 1];
         if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2]) % m;
         if ((k == '2' || k == '*') && input[i - 1] <= '6') dynArr[i] = (dynArr[i] + (dynArr[i - 2]) % m) % m;
      }
      k = c;
   }
   return p ? dynArr[n] : 0;
}

int main() {
   cout<< solve("18") <<endl;
   return 0;
}