문제 이해

알파벳을 숫자로 치환하여 암호를 만들고 싶었다.
A는 1, B는 2, ..., Z는 26으로 바꾸는 것이다.
하지만 이렇게 만들 경우 암호를 해독하는데 문제가 생길 것이다.
예를들어 11의 값이 입력될 경우, 이는 AA를 나타내는 말일 수도 있으며 K를 나타내는 말이 될 수도 있다.

만약 위 방식으로 암호화한 숫자가 주어졌을 때, 이 암호가 몇 가지의 해석 방법이 존재하는지 총 경우의 수를 구하는 문제이다.(예를들어, 11은 2가 될 것이다)

---

문제 풀이

우리는 인접해 있는 2개의 수만 비교하면 된다.
2개의 인접한 수가 11 ~ 26의 알파벳을 가지면 경우의 수가 추가될 것이고, 그렇지 않을 경우 오로지 한 가지 경우의 수밖에 존재하지 않을 것이다.
(예를 들어, 27의 경우 무조건 BG로 해석할 수 밖에 없다.)

인접해 있는 2개의 수를 비교해야 하는데, 이 때 i-1, i index에 존재하는 숫자를 확인한다고 가정하자.
이 경우 몇 가지 경우의 수를 고려해야 한다.

1. i번째 수가 0이 아닌 경우

   ⇒ 우리는 i번째 숫자 자체만으로도 암호를 해석할 수 있다.

   ⇒ 따라서, i-1번째 숫자까지로 만들 수 있는 모든 암호화 방법 개수만큼 존재할 것이다.

2. (i-1)번째 수와 i번째 수를 숫자로 표시했을 때 0보다 크고 27보다 작을 경우

   ⇒ 우리는 (i-1) index 숫자와 i index 숫자를 합쳐 하나의 알파벳으로 표현할 수 있을 것이다.

   ⇒ 이 상황을 예를 들면 25의 경우, i-1번째는 2, i번째는 5로 생각하는 것이다.

   ⇒ 이 경우, (i-1)번째 숫자까지로 만들 수 있는 암호화 방법 개수 중 (i-1)번째 index의 숫자를 단독으로 암호화 시켰을 때의 경우의 수만 존재할 것이다.

이를 배열 DP로 설명해보자.
DP[i][0] : i번째 숫자가 홀로 복호화 된 경우의 수
DP[i][1] : i번째 숫자와 (i-1)번째 숫자가 결합되어 복호화 된 경우의 수

DP[i][0] = DP[i-1][0] + DP[i-1][1](i번째 숫자가 0이 아닐 경우)
DP[i][1] = DP[i-1][0](연속된 수가 0보다 크고 27보다 작을 경우(

DP[i][0] : (i-1)번째까지의 숫자로 암호화 될 수 있는 모든 경우의 수로 값이 설정됨
DP[i][1] : (i-1)번째 수와 결합하여 알파벳이 될 경우 해당 값으로 설정됨

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[][] DP;
    // DP[i][0] : i번째 숫자가 혼자 복호화 되는 상태
	// DP[i][1] : i번째 숫자가 앞의 숫자와 결합되어 복호화 되는 상태
	static String value;
	
	static void dp() {
		if(value.charAt(0)-'0'==0) {
			return;
		}
		else {
			DP[0][0] = 1;
		}
		
		for(int i = 1;i<N;i++) {
			int first = value.charAt(i-1)-'0';
			int second = value.charAt(i)-'0';
			int tmp = 0;
			if(first!=0) {
				tmp = 10*first + second;
                // first = 0이라면 (i-1)번째 숫자와 결합하여 
                // 복호화 될 수 없을 것이다.
                // 따라서, first = 0이라면 tmp = 0으로 설정하게 하여
                // DP[i][1]을 채우지 않는다.
			}
			
			if(second!=0) {
                // second = 0이라면 0 단독으로는 복호화 불가능하므로 
                // DP[i][0] = 0으로 설정된다.
				DP[i][0] = (DP[i-1][0] + DP[i-1][1])%1000000;
			}
			
			if(tmp>0 && tmp <27) {
				DP[i][1] = DP[i-1][0];
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		value = sc.next();
		
		N = value.length();
		DP = new int[N][2];
		
		dp();
		
		System.out.println((DP[N-1][0]+DP[N-1][1])%1000000);
        // "모든" 경우의 수를 구해야 하기 때문에, 
        // DP[N-1][0] + DP[N-1][1]을 수행한다.
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과