[BOJ] 2011. 암호코드 (🥇, DP)

🔗

풀이

n길이의 암호코드가 있다면 해당 암호코드가 가질 수 있는 해석의 수는 이전의 암호코드들이 가지는 해석의 수를 포함하게 된다. 그림으로 나타내면 다음과 같다.

길이3의 암호코드 123은 (12, 3)과 (1, 23)으로 나눌 수 있다. 해석 가능한 암호는 1~26사이의 숫자들이기 때문에 27을 넘어가는 수는 해석할 수 없다. 즉 세 자리 이상의 수들 역시 해석이 불가능하기 때문에 만약 길이4의 암호코드 1234가 있다면 (1, 234)와 같이 나눠서 해석하는 것은 불가능하다. 때문에 위의 두 가지 경우만 가질 수 있다.

해당 수가 해석 가능하다는 것은 1 ~ 26 사이의 숫자여야 한다는 뜻이 된다. 그런데 이때 n-1번째 수가 0이면 10*(n-1번째 수) + n번째 수의 계산해서 1 ~ 26 사이의 숫자가 될 숫 있다. 하지만 실제로는 '02' 는 '2'로 해석될 수 없으므로 앞자리가 0인 경우는 무조건 해석이 불가능한 것으로 처리해야 한다.

해석 가능 여부를 판단하는 함수는 check1과 check2로 각각 1자리 수, 2자리 수의 수가 해석 가능한지 여부를 판단하게 된다. 결국 n번째의 1자리수가 해석이 가능하면 dp[n-1]번째 수의 해석 가능한 가지수를 가져와서 더할 수 있다. n-1번째의 수와 n번째 수 2자리수가 해석이 가능하다면 2자리의 수를 제외한 나머지 dp[n-2]번째 수의 해석 가능한 가지수를 가져와서 더할 수 있게 되는 것이다. 점화식을 정리하면 다음과 같다.

dp[n] = dp[n-1] check1() + dp[n-2] check2()

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

public class Main {
    static final int DIVIDE = 1000000;
    static int check1(int a) {
        return 0 < a && a < 10 ? 1 : 0;
    }

    static int check2(int a, int b) {
        int tmp = 10 * a + b;
        return a != 0 && 1 <= tmp && tmp <= 26 ? 1 : 0;
    }

    static int solution(int n, int[] dp, int[] arr) {
        if (arr[0] == 0) return 0;
        if (n > 1) {
            dp[1] = check1(arr[1]) + check2(arr[0], arr[1]);
            
            for (int i = 2; i < n; i++) {
                dp[i] = dp[i-2] * check2(arr[i-1], arr[i]) + dp[i-1] * check1(arr[i]);
                dp[i] %= DIVIDE;
            }
        }

        return dp[n-1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split("");
        int[] arr = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        
        int[] dp = new int[input.length];
        dp[0] = 1;
        System.out.println(solution(arr.length, dp, arr));
    }
}
``