[JAVA] 백준 2011 암호코드 _DP

 

문제:

https://www.acmicpc.net/problem/2011

 

 

접근 : 

 

 - 0 으로 시작하는 숫자가 들어오면 복호화가 불가능 하므로 0을 출력한다.

 

 - 길이가 2이상인 경우에는 복호화 한 수가 26 이하이면 2, 6 개별 수 및 26 합친 수의 경우 모두를 고려한다.

 

 - 첫 번째 글자부터 끝까지 확인하면서 정답을 구한다.

 

 

코드 구현 :

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        if(input.charAt(0) - '0' == 0){
            System.out.println(0);
            return;
        }

        int[] dp = new int[input.length()+1];
        dp[0] = 1;
        dp[1] = 1;

        int now;
        int before = input.charAt(0) - '0';

        for(int i = 2 ; i <= input.length() ; i++){
            now = input.charAt(i-1) - '0';

            if (now > 0) dp[i] += dp[i - 1];

            int temp = before * 10 + now ;
            before = now;

            if (10 <= temp && temp <= 26) dp[i] += dp[i - 2];
            dp[i] %= 1000000;
        }
        System.out.println(dp[input.length()]);
    }
}