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

문제 설명

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

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

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

문제 풀이

<25114>

2 -> 5 -> 1 -> 1 -> 4

2 -> 5 -> 1 -> 14
2 -> 5 -> 11 -> 4
2 -> 51 -> 1 -> 4 X (앞 숫자와의 합이 10(J)~26(Z)만 가능)
25 -> 1 -> 1 -> 4
25 -> 1 -> 14
25 -> 11 -> 4

 

2 -> 51 -> 1 -> 4의 경우 1~26 범위 내에만 존재해야하기 때문에 제외됩니다. 

조건 1) 1~26 범위 내에만 존재해야한다.

 <101>

1 -> 0 -> 1 X (숫자가 0이면 패스해야함)

1 -> 01 X

10 -> 1 O

 

조건 2) 현재 숫자가 0이거나 앞의 숫자가 0이면 건너뛴다. 

 

<25114 dp 처리>
dp[0] = 1
dp[1] = 1  -> (2: B)   => 1은 1~26이기때문에 +dp[i-1] / 앞에 숫자가 없기 때문에 +dp[i-2] X
dp[2] = 2  -> (2 5: BE), (25:Y) => 5는 1~26이기때문에 +dp[i-1] / 25는 10~26이기때문에 +dp[i-2] = dp[0]+dp[1] = 2

dp[3] = 2  ->  (2 5 1:BEA), (2 5 1 X), (25 1: YA)

=> 1은 1~26이기때문에 +dp[i-1] / 51은 10~26이 아니기에 +dp[i-2] X = dp[2] = 2 

dp[4] = 4  -> (2 5 1 1: BEAA), (2 5 11: BEK), (25 1 1: YAA), (25 11: YK)

=> 1은 1~26이기때문에 +dp[i-1], 11은 10~26이므로 dp[i] += dp[i-2]  = dp[2] + dp[3] = 4

dp[5] = (2 5 1 1 4: BEAAD), (2 5 11 4: BEKD), (2 5 1 14: BEAN), (25 1 1 4: YAAK), (25 11 4: YKD), (25 1 14: YAN)
 => 1은 1~26이기때문에 +dp[i-1], 14은 10~26이므로 dp[i] += dp[i-2]  = dp[3] + dp[4] = 6
 */

풀이 코드

import java.io.*;
import java.util.*;

public class Main {

    private static final int MOD = 1000000;

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

        int[] dp = new int[str.length()+1];
        dp[0] = 1;

        for(int i=1; i<=str.length(); i++) {
            int now = str.charAt(i-1) - '0';
            if(now >= 1 && now <= 9) {
                dp[i] += dp[i-1];
                dp[i] %= MOD;
            }

            if(i == 1) continue; //첫번째 글자일 경우

            int prev = str.charAt(i-2) - '0';

            if(prev == 0) continue; //0으로 시작할경우 존재 X

            int value = prev*10+now;

            if(value >= 10 && value <= 26) {
                dp[i] += dp[i-2];
                dp[i] %= MOD;
            }
        }
        System.out.println(dp[str.length()]);
    }
}

<출처>

2011번: 암호코드