[BOJ2011] 암호코드 (다이나믹 프로그래밍)

 

---

문제 링크 

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

2011번: 암호코드

---

풀이

시간 복잡도 

① bottom-up : O(N)

② top-down : O(N)

 

문제)

A를 1이라고 하고, B는 2로, 그리고 Z는 26이라 할 때, 25114 암호가 주어지면 아래의 6가지 경우가 나온다

- "BEAAD" : 2/5/1/1/4

- "BEAN" : 2/5/1/14

- "BEKD" : 2/5/11/4

- "YAAD" : 25/1/1/4

- "YAN" : 25/1/14

- "YKD" : 25/11/4

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오

 

 

직접 문제 풀이 못고, 특히 파티셔닝을 어떻게 해야 될 지 파악 되지 않아 기술 블로그 참고하여 풀이하였다

 

간단하게 살펴보도록 한다

 

DP[2]의 경우 2 + 5(B + E)와 25(Y) 두 가지를 구할 수 있다

- 이는 2 의 마지막에 5를 붙임 (DP[2] += DP[2 - 1])

- 앞에 자리(DP[0])에 25 를 붙일 수 있는 경우 (DP[2] += DP[2 - 2], 이때 DP[0] = 1 초기화가 사용된다)

 

DP[3]의 경우 2 + 5 + 1 (B + E + A) 와 25 + 1(Y + A) 두 가지를 구할 수 있다

- 25 끝에 1을 더하는 경우의 수 (DP[3] += DP[3 - 1])

- 2 (DP[1])의 끝에 51 붙일 수 있는 경우의 수인데, 알파벳 범위(1 ~ 26)가 아니므로 합산되지 않는다

 

DP[4]의 경우 2 + 5 + 1 + 1 (B + E + A + A), 25 + 1 + 1 (Y + A + A), 2 + 5 + 11(B + E + K), 25 + 11(Y + K)

- 251의 경우의 수에 뒤에 1을 추가 (DP[4] += DP[4 - 1])

- 25의 경우의 수 뒤에 11을 추가(DP[4] += DP[4 - 2]), 이때 11은 알파벳 범위(1 ~ 26)내이므로 합산 된다 

 

 

주의할 점

- "01"의 경우 1의 자리만 합산이 되야 함

- "00"의 경우 1의 자리, 10의 자리 둘다 합산되지 않음

 

 

DP 가짜 문제 정의 유형 중에서 문제 크기 N을 변수로 만들어 표기하는 방법을 다루었다

 

---

제출 코드

bottom-up 방식

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int MOD = 1000000;

    static String PASSWORD;
    static long[] DP;

    public static void main(String[] args) throws IOException {
        input();
        pro();
        output();
    }

    private static void input() {
        PASSWORD = inputProcessor.nextLine().trim();
        DP = new long[PASSWORD.length() + 1];
    }

    private static void pro() {
        // 초기화
        DP[0] = 1; 

        bottomUp();
        sb.append(DP[PASSWORD.length()]);
    }

    private static void bottomUp() {
        for(int i = 1; i <= PASSWORD.length(); i++) {
             int first = PASSWORD.charAt(i - 1) - '0';
             if(1 <= first && first <= 9) {
                 DP[i] += DP[i - 1];
                 DP[i] %= MOD;
             }

            if(i == 1) continue;

            int ten = PASSWORD.charAt(i - 2) - '0';

            if(ten == 0) continue;

            int value = ten * 10 + first;
            if(10 <= value && value <= 26) {
                DP[i] += DP[i - 2];
                DP[i] %= MOD;
            }
        }
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}

 

 

top-down 방식

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();
    static int MOD = 1000000;

    static String PASSWORD;
    static long[] DP;

    public static void main(String[] args) throws IOException {
        input();
        pro();
        output();
    }

    private static void input() {
        PASSWORD = inputProcessor.nextLine().trim();

        // DP 초기화
        DP = new long[PASSWORD.length() + 1];
        DP[0] = 1;

        int first = PASSWORD.charAt(0) - '0';
        if(1 <= first && first <= 9) {
            DP[1] = 1;
        }
    }

    private static void pro() {
        topDown(PASSWORD.length());
        sb.append(DP[PASSWORD.length()]);
    }


    private static long topDown(int idx) {
        if(idx <= 1) return DP[idx];
        if(DP[idx] != 0) return DP[idx];

        int one = PASSWORD.charAt(idx - 1) - '0';
        if(1 <= one && one <= 9) {
            DP[idx] += topDown(idx - 1);
            DP[idx] %= MOD;
        }

        int ten = PASSWORD.charAt(idx - 2) - '0';
        int value = ten * 10 + one;
        if(10 <= value && value <= 26) {
            DP[idx] += topDown(idx - 2);
            DP[idx] %= MOD;
        }

        return DP[idx];
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}