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

🔗 2011번 : 암호코드
● Java 풀이
● 시간 제한 2초
● 메모리 제한 128 MB

✅ 문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

---

✅ 테스트 케이스

/** 출처 (https://acmicpc.net/board/view/110418) **/
// input
017

// answer 
0

// input
10025

// answer
0

// input
1131212501112122

//answer
0

// input
111012

// answer
4

---

✅ 풀이

import java.io.*;

public class Main {
    private static long[] fiboNums;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String code = br.readLine();
        if (code.isBlank() || code.charAt(0) == '0') {
            System.out.println(0);
            return;
        }
        int codeLen = code.length();
        fiboNums = new long[codeLen + 1];

        long count = 1;
        int start = 0;
        for (int i = 1; i < codeLen; i++) {
            String alpha = "" + code.charAt(i - 1) + code.charAt(i);
            if (code.charAt(i) == '0') {  // 0이 발견된 경우
                if (code.charAt(i - 1) != '1' && code.charAt(i - 1) != '2') {  // 숫자를 만들 수 없는 경우
                    count = 0;
                    break;
                } else {
                    count = (count * fibo(i - 1 - start)) % 1000000;
                    start = i + 1;
                }
            } else if (26 < Integer.parseInt(alpha)) {
                count = (count * fibo(i - start)) % 1000000;
                start = i;
            }
        }
        if (start < codeLen) count = (count * fibo(codeLen - start)) % 1000000;

        System.out.println(count);
    }

    private static long fibo(int i) {
        if (i == 0) return 1;
        if (i <= 2) return fiboNums[i] = i;
        if (0 < fiboNums[i]) return fiboNums[i];

        return fiboNums[i] = (fibo(i - 1) + fibo(i - 2)) % 1000000;
    }
}

 

필자는 이 문제를 피보나치 수열로 풀었다.

• '1'이란 숫자로 만들 수 있는 암호의 경우의 수는 {'A'} 뿐이므로 1개이다.
• '11'이란 숫자로 만들 수 있는 암호의 경우의 수는 {'AA', 'K'}로 2개이다.
• '111'이란 숫자로 만들 수 있는 암호의 경우의 수는 {'AAA', 'AK', 'KA'}로 3개이다.
• '1111'이란 숫자로 만들 수 있는 암호의 경우의 수는 {'AAAA', 'AAK', 'AKA', 'KAA', 'KK'}로 5개이다.

이를 반복하다 보면 모든 자리수의 원소가 분해 가능할 때, 나타나는 경우의 수는 피보나치 수열임을 알 수 있다.

 

하지만 문제에서 주어진 숫자 '25114'를 보자. '11111'과 다르게 51이란 숫자로는 알파벳을 만들 수 없으므로 5와 1은 반드시 떨어져있어야 한다. 그렇다면, 이 숫자를 떨어뜨리는 것이다.

25 / 114의 두 숫자로 떨어뜨리고, 두 숫자에 대한 경우의 수를 곱하는 것이다.

• 2개의 자리수가 존재할 때의 경우의 수는 {'BE', 'Y'}로 2. (fiboNums[2] = 2)
• 3개의 자리수가 존재할 때의 경우의 수는 {'AAD', 'AN', 'KD'}로 3. (fiboNums[3] = 3)

떨어져야할 숫자를 떨어뜨리고, 그 두 숫자의 경우의 수를 결합하면 2 * 3 = 6의 답이 나오는 것이다.

이 방법과 마찬가지로 다른 숫자들에 대해서도 떨어져야 할 숫자까지의 숫자를 자르고, 각 자른 숫자들에 대한 경우의 수를 곱하면 정답이 나온다. (23135일 경우, 23 / 13 / 5)

 

🌠 그 외에 고려해야할 것 (0의 처리)

🔗 https://www.acmicpc.net/board/view/110418

 

위의 백준 게시글 작성자님이 너무 작성을 잘해주셔서, 이를 참고하여 설명해보고자 한다.

문제의 큰 수를 고려하는 것 자체는 어렵지 않다. 하지만 여기서 더욱 집중해야할 것은 불필요한 0이 존재하지 않는다는 것이다. 즉, 'A' 문자를 위해서 '01' 암호를 사용하는 경우가 없다는 것이다.

 

그렇다면 불필요한 0이 존재할 경우, 이는 더이상 암호가 될 수 없다는 뜻이다.

• '017' : 가장 앞에 0이 존재한다. 이 0은 어느 문자로도 바꿀 수 없고, 위에서 언급하였듯 '01'과 같이 문자열로 사용될 수 없으니, 가장 앞에 0이 존재할 경우, 암호가 될 수 없다는 것이다.
• '10012' : 0이 두개 이상 존재한다. 10으로 자를 경우, 문자가 될 수 있겠지만, 뒤의 0은 어느 문자도 될 수가 없다. 그러므로, 반복되는 0이 존재할 경우 암호가 될 수 없다는 것이다.
• '1302' : 가장 앞에 0이 존재하지도, 0이 두 개 이상 존재하지도 않으나, 앞의 숫자가 3 이상이 나왔다. 30으로 밖에 사용될 수 없는 0인데, 30의 암호를 사용하는 알파벳은 존재하지 않는다. 0의 앞에 1 혹은 2가 아닌 다른 숫자가 존재할 경우 암호가 될 수 없다는 뜻으로 알 수 있다.

필자 같은 경우에는 0을 처리해주기 위해 숫자의 자리를 각 탐색하며, 0이 나왔을 경우, 앞의 숫자가 1 혹은 2인지를 판단하고, 아닐 시 바로 0을 출력하고 프로그램을 종료하는 방식으로 작성하였다.

그리고, 숫자를 자르는 방식으로 개발했으므로, 0을 개별로 자를 수 없으니 0을 제외한 숫자로 잘랐다. 그 이유는 '2310'의 경우 231로 자르므로서, 각 숫자 원소가 3개 존재함을 나타내고 싶었기 때문이다. 자른 수 자체는 231이지만, 숫자의 개수로만 따지면 {2, 3, 10}으로 3개라는 것이다. 

 

0의 예외가 또 무엇이 존재할지 테스트 케이스를 직접 만들어보는 방식으로 풀면 좋을 듯 하다. 또한, 피보나치 수열 값에서도, 경우의 수를 곱하는 값에서도 1000000으로 나누는 것을 잊지 않길 바란다.