[Algorithm] 백준 DP 문제 - 암호코드(2011) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 암호코드 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2011

2011번: 암호코드

 

1. 풀이 소스 

 

import java.io.*;

public class Main {
    static final int MOD = 1000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String encode = br.readLine();

        if (encode.charAt(0) == '0') {
            System.out.println("0");
            return;
        }

        int len = encode.length();
        long[] dp = new long[len + 1];
        dp[0] = dp[1] = 1; // 하나로 초기화

        // dp는 1번 인덱스, 문자열은 0번
        for (int i = 2; i <= len; i++) {
            char now = encode.charAt(i - 1); // 현재 문자 판단
            char pre = encode.charAt(i - 2); // 이전 문자
            if (now == '0') {
                // 120 이 있는 경우, 20은 가능한 문자이므로 1이 있었던 위치의 dp 활용 (두개가 하나이므로)
                if (pre == '1' || pre == '2') dp[i] = dp[i - 2];
                else break;
            }
            else {
                // 앞 문자가 0인 경우 무조건 주어진 숫자 하나만 선택 가능하므로 그대로  ex) 03 -> 3
                if (pre == '0') dp[i] = dp[i - 1];
                else {
                    int num = (pre - '0') * 10 + (now - '0'); // 숫자로 만들기
                    if (1 <= num && num <= 26) dp[i] = (dp[i - 2] + dp[i - 1]) % MOD;
                    else dp[i] = dp[i - 1]; // 28의 경우 알파벳 변환 불가하므로 한개 선택 => 그대로
                }
            }
        }
        System.out.println(dp[len] % MOD);
    }
}

 

2. 풀이 중점 과정

 

해당 문제는, 문자열의 인덱스와 DP의 인덱스를 설정하는 과정이 중요하였습니다. 이 부분을 해결하지 못하여 코드를 참조하여 작성하였습니다.

 

풀이할 때, 예외 처리가 중요하였는데, 고려해야 할 사항은 다음과 같습니다.

• 시작이 0인 경우 불가
• 10, 20을 만들 수 있는 위치의 '0'이 아닌 경우 불가 ex) 30, 300
• 이전 문자와 현재 문자로 숫자를 만들었을 때, 26이 넘어가는 경우 각각 개별적인 선택만 가능 ex) 27
• 이전 숫자가 0인 경우는 현재 숫자는 2개를 만들 수 없고 선택해야 함 ( 위에서, 10, 20을 만들 수 있는 위치의 '0'이 아닌 경우에서 2개가 연속된 0인지 판단하는 로직이 있으므로 여기서는 선택)
• 만약 2개의 문자열을 만들 수 있다면 하나만 선택하기 위해 dp[i - 1] + 두 개를 문자로 묶어 하나로 만들기 위한 dp[i - 2]로 점화식을 만들 수 있습니다.

문자열은 0부터 시작하고, dp는 1부터 시작하여 

문자의 길이가 2라면, 문자열 인덱스는 0, 1 까지 이고,

dp는 dp[2]가 문자 길이 2에 대한 값을 나타내도록 하였습니다.

 

자세한 풀이는 주석으로 처리하였습니다. 이상으로 암호코드 자바 풀이를 마치도록 하겠습니다. 감사합니다.

 

풀이 참고 자료: https://iamheesoo.github.io/blog/algo-boj2011