[BOJ] 2011 암호코드 - JAVA

1. 문제

2011번: 암호코드

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

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

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

---

2. 풀이

입력받은 암호를 char배열로 만들고, 길이를 N에 저장했다.

[N][2]칸 int 배열을 만들어서 다음과 같이 저장한다. 숫자 범위에서 벗어나면 0을 저장한다.

 

dp초기값으로 dp[0][0]에 1을 저장해야하는데, password[0]이 1이상 9이하일때만 저장한다.

dp[i][0] : password[i] 한 자리 암호를 사용한 경우의 수. dp[i-1][0] + dp[i-1][1]. 단 password[i]가 1이상 9이하여야 함.

   * MOD연산을 잊으면 안 된다. dp[i-1][0], dp[i-1][1]은 모두 MOD연산이 되어있는 결과라 둘을 더한 것에만 계산하면 된다.

dp[i][1] : password[i-1]*10+password[i-1]의 두 자리 암호를 사용한 경우의 수를 저장. dp[i-2][0] + dp[i-2][1] = dp[i-1][0]. 10이상 26이하여야 함.

   * dp[i][1]에서 '01', '09'처럼 십의 자리 숫자가 0인 경우는 따로 체크할 필요 없다. password[i-1]이 0이면 범위에 벗어나서 dp[i-1][0]이 이미 0으로 저장되어있기 때문이다. 따라서 자연스럽게 dp[i][1]도 0이 된다.

 

답은 dp[N-1][0] + dp[N-1][0]인데, 이 때도 MOD연산을 잊지 않고 출력해야 한다.

import java.io.*;

public class BOJ_2011_암호코드 {
   public static void main(String[] args) throws IOException {
      char[] password = new BufferedReader(new InputStreamReader(System.in)).readLine().toCharArray();
      int N = password.length;
      int MOD = 1000000;
      int[][] dp = new int[N][2];

      if(password[0]-'0' > 0) dp[0][0] = 1;
      for(int i=1;i<N;i++){
         if(password[i]-'0'> 0) dp[i][0] = (dp[i-1][0] + dp[i-1][1])%MOD;
         if((password[i-1]-'0')*10 + password[i]-'0' <= 26) dp[i][1] = dp[i-1][0];
      }

      System.out.println((dp[N-1][0] + dp[N-1][1])%MOD);
   }
}

---

3. 결과

마지막 정답출력에도 MOD연산을 해야하는 걸 잊어서 한 번 틀렸다.

두번째 코드에서는 중간중간 dp[i][0]==0 && dp[i][1]==0이면 main을 끝내는 조건이 있었는데 어차피 이 문제의 시간복잡도는 O(N)이고 조건 체크하는 게 더 비효율적인 것 같아서 지웠다.