백준 -암호코드 (2011) : JAVA

문제 유형
dp

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.
	상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
	선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
	상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, 	BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
	선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
	상근: 얼마나 많은데?
	선영: 구해보자!
2. 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.
3. 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.
4. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

부분의 문제로 전체의 문제를 해결할 수 있기 때문에 dp를 통해서 해결할 수 있습니다.

i번째 문자를 복호화할때 두가지 경우를 고려할 수 있습니다.
1. i번째 문자만 복호화한다.
2. i-1번째 문자, i번째 문자를 복호화한다. (다만 i-1번째 문자와 i번째 문자를 이어 붙였을 때 10이상 26이하여야한다.)

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


for (int i = 2; i <= len; i++) {
    int a = word.charAt(i - 2) - '0';
    int b = word.charAt(i - 1) - '0';

    if (b == 0) {
        if (a != 1 && a != 2) {
            flag = true;
            break;
        }
    }

    if (b != 0) {
        dp[i] += dp[i - 1];
        dp[i] %= 1000000;
    }

    if (a != 0) {
        int total = a * 10 + b;

        if (total >= 10 && total <= 26) {
            dp[i] += dp[i - 2];
            dp[i] %= 1000000;
        }
    }
}    

핵심 코드는 위와 같습니다.
주의 할 점은 암호가 잘못된 경우를 처리해줘야한다는 것입니다. (아마 여기서 낮은 정답률이 형성되지 않았나 싶습니다.)
예를 들어서 100, 011, 90과 같은 암호는 잘못된 암호입니다.

시간 복잡도
O(N)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


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

        int len = word.length();
        
        int[] dp = new int[len+1];
        
        dp[0] = 1;
        dp[1] = 1;
        
        boolean flag = false;
        
        if (word.charAt(0) == '0') {
        	System.out.println(0);
        	return;
        }
       
        
        for (int i=2; i<=len; i++) {
        	int a = word.charAt(i-2) - '0';
        	int b = word.charAt(i-1) - '0';
        	
        	if (b == 0) {
        		if (a != 1 && a != 2) {
        			flag = true;
        			break;
        		}
        	}
        	
        	if (b != 0) {
        		dp[i] += dp[i-1];
            	dp[i] %= 1000000;
        	}
        	
        	if (a != 0) {
        		int total = a * 10 + b;
            	
            	if (total >= 10 && total <= 26) {
            		dp[i] += dp[i-2];
            		dp[i] %= 1000000;
            	}
        	}
        	
        }
        
        if (flag) System.out.println(0);
        else System.out.println(dp[len]);

    }
    

}