[백준 2011] 암호코드 - JAVA

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

 

 dp

언뜻 보기에는 쉬우나, 고려해야 할 경우가 많아 초기화가 까다로운 문제다.

 

 

1. 유효한 수의 범위는 1~26이다.

따라서, 한 자리 수는 0이면 안된다.

 

2. '수'에 다음과 같은 경우는 포함되지 않는다. 01 001 0023

따라서, 두 자리 수는 10~26 범위만 유효하다.

또는, 첫 자리가 0이 아니고 27보다 작으면 된다.

 

3. 1번과 2번에 따라, 암호의 첫 번째 수가 0이면 경우의 수는 무조건 0이다.

 

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s = br.readLine();
    int n = s.length();
    int MOD = 1_000_000;

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

    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
      int oneDigit = s.charAt(i - 1) - '0';
      int twoDigit = Integer.parseInt(s.substring(i - 2, i));

      if (oneDigit >= 1) {
        dp[i] += dp[i - 1];
        dp[i] %= MOD;
      }

      if (twoDigit >= 10 && twoDigit <= 26) {
        dp[i] += dp[i - 2];
        dp[i] %= MOD;
      }
    }

    System.out.println(dp[n]);
  }
}