백준 2011번 : 암호코드 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

암호코드 골드 5

 

📖 문제

 

DP 문제 연습셋

DFS + DP (메모이제이션)으로 풀었는데 좀 더럽게 풀었다.

DP[암호의 각 인덱스][알파벳 인덱스] 이렇게 2중 배열로 생각해서 풀었다. 

그런데 알파벳은 고려대상이 아니다. 

 

 

다른 사람 풀이를 보고 이해한 것도 정리한다.

 

0에 대한 모든 경우의 수를 처리했는데 그럴필요가 없었다...

 

 

그리고 DFS로 풀때 idx 즉, 인덱스만 신경쓰면 충분히 풀이가 가능했다. 나는 굳이 알파벳 수치 값을 파라미터로 넘겼는데 

그럴 필요없이 현재 선택한 수가 알파벳 변환이 가능한지 여부로 따지고 가능하다면 다음 인덱스로 넘어가는 식으로 하면된다. 

 

 

비슷한 문제 포스팅

https://progis.tistory.com/85

---

🔅 문제 풀이 [내 풀이 Top-Down]

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

public class Main {
    static final int MOD = 1000000;
    // 자릿수, 수
    static int[][] dp;
    static String code;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        code = br.readLine();
        dp = new int[code.length()][27]; // 암호문 길이, 1~26 알파벳 인덱스


        if (code.startsWith("0") || code.matches(".*00.*") || code.matches(".*[3-9]0.*")) {
            System.out.println(0);
            return;
        }

        // -1로 초기화
        for (int i = 0; i < code.length(); i++) {
            Arrays.fill(dp[i], -1);
        }


        int answer = dfs(0, code.charAt(0) - '0') % MOD;


        if (code.length() >= 2 && code.charAt(0) != '0') {
            answer += dfs(1, (code.charAt(0) - '0') * 10 + code.charAt(1) - '0') % MOD;
        }

        System.out.print(answer % MOD);
    }

    private static int dfs(int idx, int alpha) {
        // 범위 벗어난 것은 0 반환
        if (idx > code.length() || alpha <= 0 || alpha > 26) {
            return 0;
        }

        if (idx == code.length() - 1) {
            return 1;
        }

        // 이미 탐색한 경로라면 경우의 수 반환
        if (dp[idx][alpha] != -1) {
            return dp[idx][alpha];
        }

        // 처음 방문이므로 0으로 초기화
        dp[idx][alpha] = 0;

        if (idx + 1 < code.length()) {
            dp[idx][alpha] += dfs(idx + 1, code.charAt(idx + 1) - '0');
        }
        if (idx + 2 < code.length() && code.charAt(idx + 1) != '0') {
            dp[idx][alpha] += dfs(idx + 2, (code.charAt(idx + 1) - '0') * 10 + code.charAt(idx + 2) - '0');
        }


        return dp[idx][alpha] % MOD;
    }

}

 

🔅 문제 풀이 [Top-Down]

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

public class Main {
    static final int MOD = 1000000;
    static int[] dp;
    static String code;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        code = br.readLine();

        int n = code.length();
        dp = new int[n + 1];
        Arrays.fill(dp, -1);

        // 유효하지 않은 시작 조건
        if (code.charAt(0) == '0') {
            System.out.println(0);
            return;
        }

        System.out.println(dfs(0));
    }

    private static int dfs(int idx) {
        if (idx == code.length()) return 1;
        if (dp[idx] != -1) return dp[idx];

        int result = 0;

        // 한 글자
        int one = code.charAt(idx) - '0';
        if (one >= 1 && one <= 9) {
            result += dfs(idx + 1);
        }

        // 두 글자
        if (idx + 1 < code.length()) {
            int two = Integer.parseInt(code.substring(idx, idx + 2));
            if (two >= 10 && two <= 26) {
                result += dfs(idx + 2);
            }
        }

        return dp[idx] = result % MOD;
    }
}

 

🔅 문제 풀이 [Bottom-Up]

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

public class Main {
    static final int MOD = 1000000;
    static int[] dp;
    static String code;

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

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

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

        for (int i = 2; i <= n; i++) {
            int first = code.charAt(i - 1) - '0';
            int second = code.charAt(i - 2) - '0';
            int num = second * 10 + first;

            if (first != 0) {
                dp[i] += dp[i - 1];
            }

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

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

 

❗ 오답노트 / 필요한 지식

1. 간단하게도 생각해보자.