백준 2011번 - 암호코드

문제

백준 2011번 - 암호코드

아이디어

• dp[n]을 n번째 자리에서 가능한 가지수라 가정한다.
• 첫번째 자리가 0이면 잘못된 암호다.
• 첫번째 자리는 무조건 하나로만 해석할 수 있으므로 dp[1] = 1로 초기화하고, 두번째 자리부터 구한다.
• 해당 자리의 수가 0이 아니면, 이전 경우의 수에서 해당 자리의 수만 그대로 붙여서 읽을 수 있으므로 이전 경우의 수를 그대로 따라간다. 또한 이전 자리수와 조합으로 10~26 사이이면 두 글자씩 해석이 가능하다. 이 경우 현재 경우의 수에 2번째 전 자리에서 가능한 경우의 수를 더해줄수 있다.
• 예를 들어 1111의 경우 4번째 경우의 수를 구할 때 111의 모든 경우의 수에 대해 마지막 1만 붙일 수 있으므로 이전 경우의 수를 그대로 따라간다. 그리고 세번째 1과 조합으로 정상범위인 11을 만들 수 있고, 두자리 전에서 가능한 경우의 수에 현재 11을 붙일 수 있다는 뜻이다. 그러므로 두자리 전에서 가능한 경우의 수까지 더해줄 수 있다.
• 해당 자리가 0인 경우는 0만을 단독으로 해석할 수 없으므로 0만 붙이는 경우는 건너뛰고, 이전 자리와의 조합만 살펴보게 된다.

예상 시간 복잡도

• 암호의 길이 : N
• 예상 시간 복잡도 : O(N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ_2011 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] arr = br.readLine().toCharArray();

        if (arr[0] == '0') {
            System.out.println(0);
            return;
        }

        int[] dp = new int[arr.length + 1];
        dp[0] = dp[1] = 1;

        for (int i = 2; i <= arr.length; i++) {

            //-1이라 헷갈릴 수 있는데 해당 자리를 보는 것이다.
            if (arr[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }

            //이것도 해당 자리와 이전 자리의 조합이다.
            int num = (arr[i - 2] - '0') * 10 + (arr[i - 1] - '0');

            if (10 <= num && num <= 26) {
                dp[i] += dp[i - 2];
            }

            dp[i] %= 1_000_000;
        }

        System.out.println(dp[arr.length]);

    }
}