[JAVA] 백준 (골드5) 2011번 암호코드

링크

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

---

입력 예제

25114

---

출력 예제

6

---

풀이

첫번째 숫자부터 탐색해가면서 방법의 수를 구해보면

• 첫번째
  • 2
• 두번째
  • 2, 5
  • 25
• 세번째
  • 2, 5, 1
  • 25, 1
• 네번째
  • 2, 5, 1, 1 -> 세번째
  • 25, 1, 1 -> 세번째
  • 2, 5, 11 -> 두번째
  • 25, 11 -> 두번째
• 다섯번째
  • 2, 5, 1, 1, 4 -> 네번째
  • 25, 1, 1, 4 -> 네번째
  • 2, 5, 11, 4 -> 네번째
  • 25, 11, 4 -> 네번째
  • 2, 5, 1, 14 -> 세번째
  • 25, 1, 14 -> 세번째

i번째 숫자가 한자리 수일 경우 i-1번째 까지의 방법에 i번째 수만 추가한 경우가 되고, i번째 숫자가 두자리 수의 일의 자리가 될 경우는 i-2번째 까지의 방법에 두자리 수를 추가한 경우가 된다.

따라서 dp배열은 다음과 같이 정의한다.

dp[i]: i번째 문자까지의 부분 문자열을 해석할 수 있는 경우의 수

한자리 숫자로 처리할 경우는 dp[i] += dp[i - 1], 두자리 숫자로 처리할 경우는 dp[i] += dp[i - 2]가 된다.

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        int n = s.length();
        int[] arr = new int[n + 1];
        //dp[i]: i번째 문자까지의 부분 문자열을 해석할 수 있는 경우의 수
        int[] dp = new int[n + 1];
        int mod = 1_000_000;

        for (int i = 1; i <= n; i++) {
            arr[i] = s.charAt(i - 1) - '0';
        }

        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            //한자리 숫자 처리
            if (arr[i] > 0) {
                dp[i] += dp[i - 1];
                dp[i] %= mod;
            }

            //두자리 숫자 처리
            if (i > 1) {
                int x = arr[i - 1] * 10 + arr[i];  //두자리 숫자 생성
                if (x >= 10 && x <= 26) {  //A ~ Z
                    dp[i] += dp[i - 2];
                    dp[i] %= mod;
                }
            }
        }

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