[백준] 2011번 - 암호코드 (Gold 5)

문제 링크

[백준] 2011번 - 암호코드 (Gold 5)

문제 설명

평문을 A를 1로, B를 2로, $\cdots$, Z를 26으로 암호화한다.
암호문이 주어졌을 때, 가능한 평문의 개수를 1000000으로 나눈 나머지를 출력한다.

정답 코드 및 설명

암호문 arr[]를 앞에서부터 i번째까지 끊었을 때 가능한 평문의 개수 count[i]로 점화식을 세운다.
i+2번째까지 끊었을 때 가능한 평문의 개수 count[i+2]를 구해보자.

1. 평문의 마지막 문자가 암호문의 마지막 한자리 숫자를 복호화 한 문자인 경우
   • 암호문의 마지막 자리가 0이어서는 안된다.
   • 위 조건을 만족한다면 count[i+1]가지의 평문이 가능하다.
2. 평문의 마지막 문자가 암호문의 마지막 두자리 숫자를 복호화 한 문자인 경우
   • 암호문의 마지막 두 자리가 10 이상 26 이하이다.
   • 위 조건을 만족한다면 count[i]가지의 평문이 가능하다.

이를 코드로 구현하면 아래와 같다.

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

public class BOJ2011 {
    int[] arr;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String enc = br.readLine();
        arr = new int[enc.length()];
        for (int i = 0; i < arr.length; i++)
            arr[i] = enc.charAt(i) - '0';
    }

    int dp() {
        int[] count = new int[arr.length + 1];
        count[0] = 1;
        for (int i = 1; i <= arr.length; i++) {
            // 첫 한 글자인 경우
            if (i == 1) {
                if (arr[i - 1] == 0) return 0;
                count[i] = 1;
                continue;
            }
            // 뒤의 두 자리가 문자로 변환되지 않는 경우
            if (arr[i - 2] * 10 + arr[i - 1] > 26 || arr[i - 2] == 0) {
                if (arr[i - 1] == 0) return 0;
                count[i] = count[i - 1];
                continue;
            }
            // 뒤의 두 자리가 문자로 변환이 가능한 경우
            count[i] = count[i - 2];
            if (arr[i - 1] != 0) {
                count[i] += count[i - 1];
                count[i] %= 1000000;
            }
        }
        return count[arr.length];
    }

    void solution() throws IOException {
        input();
        System.out.println(dp());
    }

    public static void main(String[] args) throws IOException {
        new BOJ2011().solution();
    }
}