2011번 : 암호코드 [JAVA]

암호코드 링크

문제

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

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

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

입력

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

출력

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

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

예제 입력 1 복사

25114

예제 출력 1 복사

6

예제 입력 2 복사

1111111111

예제 출력 2 복사

89

성공 여부(걸린 시간): 실패(56분) -> 반례보다가 코드를 봐버림

아이디어

처음에 시작은 순조로웠다. 일단 점화식은 잘 작성했는데

앞 숫자가 1~2라면
DP[i] = Math.max(DP[i-1]+DP[i-2], DP[i]);
아니면 그대로

그런데 왜 이렇게 많이 틀렸나 궁금할 것이다.

만약 2101이란 숫자가 있다면
내가 이해한 그대로라면 [2, 10, 1], [21, 01] 이런식으로 01도 1아닌가? 생각을 했으나 이렇게 풀면 안되는 것이었다.

01 02 이건 불가능하다는점 확실히 하고 풀면 좋을듯

 

그 외에도 기본적인 로직에서 추가로 예외 처리들을 해주어야 했는데 크게 생각할것은 아래와 같다.

1. 일단 시작이 0인 경우는 무조건 불가능한 암호이다.(01,02 이런건 없다.)
2. 마지막 글자가 0인데 그 앞글자가 0이나 3이상의 수라면 0을 불가능한 암호이다.
3. 불가능한 수가 아닐 경우에 앞의 숫자가 3 이상이거나 0이라면 그냥 이전 저장값을 그대로 넣어준다.
4. 만약 10, 20이 아니고 2자리 수가 가능하면 점화식적용
5. 10이나 20인 경우는 그 자체로 하나의 경우밖에 없기에 i-2번째 dp값 넣어준다.

정답 코드

import java.io.*;
class Main{
    public static void main(String [] args)throws IOException{
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        String code = br.readLine();
        //시작하기에 앞서 무조건 안되는 경우 처리
        if(code.charAt(0)=='0'||(code.charAt(code.length()-1)=='0'&&code.charAt(code.length()-2)-'0'>2)){
            System.out.print(0);
            return;
        }
        int [] dp = new int[code.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=code.length(); i++){
            dp[i] = dp[i-1];
            int x = Integer.parseInt(code.substring(i-2, i));
            if(x==0||x%10==0&&x/10>=3){//0이나 30
                System.out.print(0);
                return;
            }
            else if(x<=26&&x>=10){
                if(x==10||x==20){
                    dp[i]=dp[i-2];
                }
                else{
                    dp[i]= Math.max(dp[i], dp[i-2]+dp[i-1])%1000000;
                }

            }
        }
        System.out.print(dp[code.length()]);
    }
}