[ 백준 ] 2011 암호코드

📌 Problem

암호는 A = 1 ~ Z = 26으로 해석한다. 0부터 9까지의 수로 이루어진 5000자리 이하의 암호가 주어졌을 때 총 몇개의 암호로 해석될 수 있는지 구하면 된다. 만약 암호문이 해석될 수 없다면 0을 출력한다. 예를 들어, 11은 AA로 해석할 수도 있지만 동시에 K로 해석될 수도 있다. 하지만 10의 경우는 J로만 해석될 수 있다.

📌 Solution

단일 해석 제거
동적 프로그래밍으로 해결할 수 있다. 하지만 동적 프로그래밍을 구하기 전에 암호에서 무조건 하나로만 해석되는 것을 제외한다. 여기에는 10과 20이 있다. 예를 들어 1232031에서 중간에 있는 0은 혼자서 해석될 수 없다. 앞에 있는 문자와만 해석이 가능하다. 이는 10에서도 마찬가지이다. 그렇기 때문에 10과 20은 사전에 제외한다.

reader.readLine().replaceAll("[12]0", "-");

공백이 아니라 -으로 변환하는 이유는 앞뒤의 암호가 연결되는 것을 방지하기 위함이다. 예를 들어 1101이 있을 때 10은 하나로만 해석되기 때문에 1 10 1으로 해석하는 한 가지 방법만이 존재한다. 그런데 10을 완전히 제거해버리면 앞의 1과 뒤의 1이 붙어서 11이 되며 1 1 또는 11로 해석될 수 있다. 그렇기 때문에 완전히 제거하는 것이 아닌 표시를 하는 것이다.

암호 해석
이 연산을 하고 나면 암호 자체가 잘못되지 않은 경우 1과 9로만 이루어져 있다. 한 문자씩 탐색을 하면서 이전 문자와 비교하면 된다. 이에 대한 점화식은 다음과 같다.

int connect = Character.getNumericValue(pre) * 10 + Character.getNumericValue(cur);
if (10 < connect && connect <= 26) dp[i] = (dp[i - 1] + dp[i - 2]) % 1_000_000;
else dp[i] = dp[i - 1];

이전 문자와 연결을 했을 때 하나의 문자로 판단이 되면 그 이전의 dp 값과 이전 dp 값을 더한다. 만약 하나의 문자로 판단되지 않는다면 이전 dp값을 그대로 가져온다. 예를 들어 8911을 생각해보자. 첫 번째 문자는 이전 문자가 없기 때문에 하나로만 판단할 수 있다. dp[0] = 1. 9는 이전 문자 8과 결합하여 판단 할 수 없으니 이전 값을 그대로 가져온다. dp[1] = dp[0]. 세 번째 문자도 마찬가지로 이전 문자와 결합할 수 없다 dp[2] = dp[1]. 네 번째 문자인 1은 이전 문자인 1과 결합하여 11로 해석될 수 있다. 그렇기 때문에 결합하지 않은 경우 dp[2]과 결합한 경우 dp[1]를 더한다 dp[3] = dp[2] + dp[1]. 이 때 문제에서 1,000,000의 나머지 값으로 구하라고 했기 때문에 나머지 연산을 같이 수행한다.

중간 해석
그런데 사실 암호문에는 단일 해석을 통한 - 문자와 잘못된 암호의 경우 0이 포함되어 있다. 이를 다음과 같이 처리한다.
1. 탐색한 문자가 - 이면 이전 dp 값을 그대로 가져온다. dp[i] = dp[i - 1]
2. 탐색한 문자가 0이면 잘못된 암호문이므로 모든 연산을 종료한다. dp[dp.length - 1]은 0으로 초기화되어 있다.
3. 이전 문자가 - 이면 현재 탐색 문자는 혼자서만 해석이 가능하므로 이전 값을 가져온다. dp[i] = dp[i - 1]

📌 Code

String code = 9 + reader.readLine().replaceAll("[12]0", "-");
int[] dp = new int[code.length()];
dp[0] = 1;
for (int i = 1; i < code.length(); i++) {
    char pre = code.charAt(i - 1);
    char cur = code.charAt(i);

    if (cur == '-') {
        dp[i] = dp[i - 1];
        continue;
    }
    if (Character.getNumericValue(cur) == 0) break;
    if (pre == '-') {
        dp[i] = dp[i - 1];
        continue;
    }
    int connect = Character.getNumericValue(pre) * 10 + Character.getNumericValue(cur);
    if (10 < connect && connect <= 26) dp[i] = (dp[i - 1] + dp[i - 2]) % 1_000_000;
    else dp[i] = dp[i - 1];
}
result.append(dp[dp.length - 1]);