[백준 2011]암호코드(Java)

문제

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

풀이

DP를 이용해 풀었다.
dp[i] = 0번째부터 i번째 글자까지의 암호의 해석의 수 라고 했을 때,
i번째 글자가 1부터 9까지인 경우에 dp[i] = dp[i]+dp[i-1]이 가능하다.
또한, i-1번째 글자와 i번째 글자를 합쳤을때 10~26일 경우에 이 또한 한 알파벳이 될 수 있으므로
이 경우에도 dp[i] = dp[i]+dp[i-2]이 가능하다.

이 문제는 암호 해독이 불가능한 예외 케이스를 많이 신경써야 한다.
만약 i번째 글자가 0일 때, i-1번째 글자가 1이나 2일 경우에는 i-1번째 글자와 i번째 글자를 합쳐서 알파벳을 만들 수 있지만,
그렇지 않은 경우에는 알파벳을 만들지 못한다.

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) throws IOException {
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        System.out.println(solution(str));
    }
    public static int solution(String str){
        char[] charArr = str.toCharArray();
        int N = charArr.length;
        if(N==0 || charArr[0]=='0') return 0;
        int[] dp = new int[N];
        dp[0] = 1;
        if(N==1) return 1;

        int left = Integer.parseInt(Character.toString(charArr[0]));
        int right = Integer.parseInt(Character.toString(charArr[1]));

        if(left>2 && right==0) return 0;

        int tmp = left*10 + right;
        if (tmp>=10 && tmp<=26 && right>0) dp[1] = 2;
        else dp[1] = 1;

        for(int i=2;i<N;i++){
            left = Integer.parseInt(Character.toString(charArr[i-1]));
            right = Integer.parseInt(Character.toString(charArr[i]));

            if(left==0 && right==0) return 0;
            else if(left>2 && right==0) return 0;
            if(right!=0) dp[i] += dp[i-1]%1000000;

            tmp = left*10 + right;
            if(tmp>=10 && tmp<=26) dp[i] += dp[i-2]%1000000;

            dp[i] = dp[i]%1000000;
        }
        return (dp[N-1]%1000000);
    }
}