암호코드 - 백준 2011 (Java)

 

나의 풀이

 맨 처음엔 각 자릿수를 1자리 혹은 2자리로 나누는 전체 경우의 수를 구하면 된다고 생각해 DFS로 접근하려 했다. 하지만 주어진 암호의 자릿수가 최대 5000자리라 다른 방법을 고민해야했다. dp로 접근이 가능해보여 시도했다.

 그리고 암호가 잘못된 경우가 어떨 때인지 생각해보니 '0'을 고려해줘야 했다. 

0의 앞자리가 1 혹은 2가 아닐 경우 잘못된 암호

 

 그 이유는 0은 10, 20일 때만 해석이 가능하기 때문이다.

 이를 토대로 규칙을 찾아보면 다음과 같다. 

dp[n] = dp[n-1] (맨 마지막 숫자가 0이 아닐 때) + dp[n-2] (뒤 두 자리의 수가 10이상 26이하일 때)

dp[n]은 n자리 암호 해독이 가능한 경우의 수

 

이를 토대로 코드를 작성하면 아래와 같다.

 

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    char[] charArr = bf.readLine().toCharArray();

    //맨 첫 숫자가 0일 때에도 잘못된 암호
    if (charArr[0]=='0') {
        System.out.println(0);
        return;
    }

    //dp 저장할 배열
    long[] dp = new long[charArr.length+1];
    //초기값 (dp[1]은 맨 첫 숫자가 0일 때를 제외했으므로 1로 초기화)
    dp[0] = 1;
    dp[1] = 1;

    //직전 자리의 숫자
    char prev = charArr[0];

    for (int i = 1; i < charArr.length; i++) {
        //현재 자릿수(i+1)에서 해석 가능한 경우의 수
        long cnt = 0L;
        //현재 숫자가 0이고 이전 숫자가 1 혹은 2가 아닐 때 잘못된 암호
        if (charArr[i]=='0' && !(prev == '1'||prev == '2')) {
            System.out.println(0);
            return;
        }
        //마지막 숫자가 0이 아닐 경우 + dp[n-1]
        if (charArr[i]!='0') {
            cnt += dp[i];
        }
        //마지막 두 자리의 숫자가 10이상 26이하일 경우 + dp[n-2]
        int lastTwo = (charArr[i-1]-'0')*10 + (charArr[i]-'0');
        if (lastTwo>=10 && lastTwo<=26) {
            cnt += dp[i-1];
        }
        //최종 cnt를 1000000으로 나눈 나머지로 dp[i+1] 갱신
        dp[i+1] = cnt%1000000;
        //직전 자리 숫자 갱신
        prev = charArr[i];
    }//for end

    System.out.println(dp[charArr.length]);
}//main() end