[백준] 2011. 암호코드

https://www.acmicpc.net/problem/2011

 

쉬운듯하지만 신경쓸게 있고, 구현 과정에서 실수하기 좋은(헷갈리는..) 부분이 많아서 푸는데 시간이 좀 걸렸다.

 

우선 dp로 풀 수 있는 문제이다. 25114가 주어졌을 때, 먼저 2를 만드는 경우부터 25, 251, ... , 25114를 만드는 경우까지 생각해보자.

• 2 -> dp[1] = 1
  • 2
• 25 -> dp[2] = 2
  • 2 + 5
  • 25
• 251 -> dp[3] = 2 
  • 2 + 5 + 1
  • 25 + 1
• 2511 -> dp[4] = 4
  • 2 + 5 + 1 + 1
  • 25 + 1 + 1
  • 2 + 5 + 11
  • 25 + 11
• 25114 -> dp[5] = 6
  • 2 + 5 + 1 + 1 + 4
  • 25 + 1 + 1 + 4
  • 2 + 5 + 11 + 4
  • 25 + 11 + 4
  • 2 + 5 + 1 + 14
  • 25 + 1 + 14

이렇게 직접 써가며 풀어보면, 규칙이 보인다. 251의 경우, 새로 추가된 수가 1이고, 1이 추가됨으로써 생성된 수는 51(251)이다. 그런데 51은 암호가 될 수 없다. 따라서 251은 25로 만들었던 암호에 1만 더한 값이다. 즉, dp[i] = dp[i - 1]이다.

 

반면 2511의 경우, 새로 추가된 수가 1이고, 1이 추가됨으로써 생성된 수는 11(2511)이다. 11은 암호가 될 수 있다. 따라서 2511은 251로 만들었던 암호에 1을 더한 경우와 25로 만들었던 암호에 11을 더한 경우이다. 즉, dp[i] = dp[i - 1] + dp[i - 2]이다.

 

결론적으로 점화식은 다음과 같다.

* 새로 만들어지는 수가 1~26 범위 내이면, dp[i] = dp[i - 1] + dp[i - 2]
* 새로 만들어지는 수가 1~26 범위 밖이면, dp[i] = dp[i - 1]

 

그리고 0이 포함되는 경우를 주의해야 한다.

• 특정 자리수 i의 값이 0이면, 무조건 그 앞자리와 합친 값으로 암호를 생성해야 한다. 그리고 이때 합친 값의 범위도 체크해줘야 한다.(10 이상 && 30 미만)
  • 10인 경우, 1 + 0이 될 수 없고 무조건 앞 자리와 합친 10만 될 수 있다.
  • 30인 경우, 30은 암호 범위를 벗어나므로 암호를 해석할 수 없어 0을 출력해야 한다.
• 만약 특정 자리수 i의 값이 0이 아니더라도, 그 앞자리와 합칠 때 앞자리가 0인 경우를 고려해야 한다. (합친 값의 범위 = 10이상 && 26 이하)
  • 이어지는 숫자가 11인 경우, 범위 내의 값이므로 암호가 될 수 있다.
  • 이어지는 숫자가 01인 경우, 두 수를 합칠 수 없다.
  • 이어지는 숫자가 41인 경우, 범위 밖의 값이므로 암호가 될 수 없다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        final int mod = 1000000;
        String code = br.readLine();
        int[] dp = new int[code.length() + 1];

        dp[0] = 1;

        // dp[i]의 값 채우기
        for (int i = 1; i <= code.length(); i++) {
            int num = code.charAt(i - 1) - '0';

            if (i == 1) {
                // 제일 첫 번째 숫자가 0이면 해석 불가!
                if (num == 0) {
                    System.out.println(0);
                    return;
                } else {
                    dp[i] = 1;
                }
                continue;
            }

            // 이번 숫자가 0인 경우, 앞자리와 합치기
            if (num == 0) {
                // 이번 숫자의 앞 숫자가 범위 밖이면 해석 불가!
                int prev = code.charAt(i - 2) - '0';
                if (prev <= 0 || prev >= 3) {
                    System.out.println(0);
                    return;
                }

                dp[i] = dp[i - 2] % mod;
            } else {
                int prev = code.charAt(i - 2) - '0';
                int connectedNum = prev * 10 + num;

                // 이어지는 숫자가 범위 안 -> dp[i] = dp[i - 1] + dp[i - 2]
                if (connectedNum >= 10 && connectedNum <= 26) {
                    dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
                }

                // 이어지는 숫자가 범위 밖 -> dp[i] = dp[i - 1]
                else {
                    dp[i] = dp[i - 1] % mod;
                }
            }
        }
        System.out.println(dp[code.length()]);
    }
}