[백준] 2011: 암호코드 - JAVA

10 Aug 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

A를 1, Z를 26으로 알파벳 각각 숫자를 매겼을 때,

숫자가 주어지고 그 숫자를 어떤 알파벳 조합으로 해석할 수 있는지 경우의 수를 찾는 문제였다.

현재 보고있는 수와 앞자리수를 붙여 26이하가 나오면 두개를 묶어 하나의 알파벳으로 바꿀 수 있게 된다.

주어진 수를 하나씩 저장해 탐색하면서

현재 숫자가 0이면 앞자리 수가 1일때 10으로 볼 수 있으므로 dp[i-2]값을 가져오고,

앞자리 숫자가 1이 아니라면 0 하나는 어떠한 알파벳으로 볼 수 없으므로 해석할 수 없는 경우로 0을 출력한다.

현재숫자가 0이 아니라면

앞자리 숫자와 붙여 10~26의 경우 dp[i-2]의 값도 가져와야 하고

나머지 경우 dp[i-1]의 값을 가져온다.

---

메모리: 14192KB

시간: 124ms

언어: Java 11

코드

import java.io.*;

public class Main {
    static final int MOD = 1_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int[] arr = new int[s.length() + 1];
        for (int i = 1; i <= s.length(); i++) {
            arr[i] = s.charAt(i - 1) - '0';
        }

        if (arr[1] == 0) {
            System.out.println(0);
        } else {
            int[] dp = new int[s.length() + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= s.length(); i++) {
                if (arr[i] == 0) {
                    if (arr[i - 1] == 1 || arr[i - 1] == 2) {
                        dp[i] += dp[i - 2] % MOD;
                    } else {
                        break;
                    }
                } else {
                    int num = arr[i - 1] * 10 + arr[i];
                    if (num <= 26 && num >= 10) {
                        dp[i] += dp[i - 2] % MOD;
                    }
                    dp[i] += dp[i - 1] % MOD;
                }

            }

            System.out.println(dp[s.length()] % MOD);
        }
    }

}