[Gold V] 암호코드 - 2011 (Java)

문제 링크

분류

다이나믹 프로그래밍

 

문제 설명

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

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

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

 

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

 

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

 

풀이 (동적 프로그래밍 바텀 업)

시간 복잡도 O(n) 공간 복잡도 O(n)

아이디어: dp[i]를 "첫 번째 문자부터 i번째 문자까지의 부분 문자열을 해석하는 방법의 수"라고 정의

현재의 문자가 하나의 문자로 해석될 수 있다면 dp[i] += dp[i-1] 

이전 문자까지 포함하여 하나의 문자로 해석될 수 있다면 dp[i] +=dp[i-2]

단 주의할 점은 문제에도 나와 있든 %1000000을 해주는 작업을 수시로 해주어야 한다. 

 

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

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    static int MOD = 1000000;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String code = br.readLine();
        int n = code.length();
        int[] dp = new int[n+1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            int head = code.charAt(i-1)-'0';
            if(head>=1 && head<=9){
                dp[i] +=dp[i-1];
                dp[i]%= MOD;
            }
            if(i==1) continue;
            int tail = code.charAt(i-2)-'0';
            if(tail==0) continue;
            int curr = tail*10+head;

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