[BOJ2011] 암호코드

암호코드

생각

문제 이해

• 최대 5000자리의 숫자가 주어졌을 때, 몇가지의 문자로 해석될 수 있는지 경우의 수를 구하는 문제
• 1 - A, 26 - Z 로 치환
  • 11 - AA 혹은 K
  • 20 - T

문제 접근

• backtracking으로는 풀 수 없는 문제 -> dp문제?
• dp[i][j]: i번째 숫자를 j자리 1의 자리로 인식하여 만들 수 있는 해석의 최대 가지 수

  0	2	5	1	1	4
  0	0	0	0	0	0
  1	1	1	2	2	4
  2	0	1	0	2	2

• 2가지 경우와 그에 따른 조건(ex N번째 수)
  • 1자리 숫자:
    • 1~9 사이어야 알파벳으로 변환 가능
    • (N-1)번째 수에서 2가지의 경우를 모두 더한 경우의 수가 답
  • 2자리 숫자:
    • 10~26 사이어야 알파벳으로 변환 가능
    • (N-2)번째 수에서 2가지의 경우를 모두 더한 경우의 수가 답

결과

런타임 에러로 실패

처음 작성한 코드는 숫자가 2글자 이상일 때에만 적상적으로 작동하는 코드였기 때문에, 초기값을 넣어줄 때 발생하는 에러였다.
그래서 무조건 1자리의 입력은 들어올테니, 1자리의 초기값은 substring으로 넣어주고, 그 이후는 문자열의 길이가 2자리인지 검사한 이후, 초기값을 넣어주고 dp배열을 채워주는 로직으로 문제를 풀이하였다.

코드

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

public class Main
 {
    static final int DIVISOR = 1000000;
    static final int MN = 5005;
    static String pw;
    static int[][] dp = new int[MN][4];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        pw = br.readLine();
        int N = pw.length();

        int n1 = Integer.parseInt(pw.substring(0, 1));
        if(0 < n1 && n1 < 10) dp[1][1] = 1;
        if(N >= 2) {
            int n2 = Integer.parseInt(pw.substring(1, 2));
            int n3 = Integer.parseInt(pw.substring(0, 2));

            if(0 < n2 && n2 < 10) dp[2][1] = dp[1][1];
            if(10 <= n3 && n3 <= 26) dp[2][2] = 1;

            for(int i=2; i<N; ++i) {
                int num = Integer.parseInt(pw.substring(i, i+1)); 
                //1자리 수
                if(0<num && num <=9) {
                    dp[i+1][1] = (dp[i][1] + dp[i][2]) % DIVISOR ;
                }
                //2자리 수 
                int prev = Integer.parseInt(pw.substring(i-1, i+1)); 
                if(10<= prev && prev <= 26) {
                    dp[i+1][2] = (dp[i-1][1] + dp[i-1][2]) % DIVISOR;
                }
            }
        }

        sb.append((dp[N][1] + dp[N][2]) % DIVISOR);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}