[백준] 암호코드

참고 : www.acmicpc.net/problem/2011

2011번: 암호코드

 

- dp 문제

- dp[i] : dp[i] + dp[i-1] (1~9 사이일 경우)

- dp[i] : dp[i] + dp[i-1] + dp[i-2] (10~26사이일 경우) 두자리 수 고려

- 가장 깔끔하신 분 풀이 보고 찾아보았다. (github.com/hotehrud/acmicpc/blob/master/algorithm/dp/2011.java)

 

import java.util.*;

public class Solution {

    private static String n;
    private static int[] dp;
    private static int[] arr;
    private static int MOD = 1_000_000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextLine();
        int len = n.length();

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

        dp[0] = 1;

        for (int i = 1; i <= len; i++) {

            if(arr[i] != 0) dp[i] = (dp[i] + dp[i-1]) % MOD;

            int overTen = arr[i] + arr[i-1] * 10;

            if(10 <= overTen && overTen <= 26) dp[i] = (dp[i] + dp[i-2]) % MOD;

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