[JAVA] BOJ 백준 2011번 - 암호코드

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

dp 알고리즘에서 bottom-up 방식을 사용해 풀었다. 보통은 top-down 방식을 사용하는데, 이번 문제는 문자열의 제일 첫 번째 문자부터 확인하면서 카운팅 해야 하기 때문에 bottom-up 방식을 사용했다.

 

첫 번째 문자는 무조건 한 가지 방법을 가지고 있으므로 dp[0] = 1 로 두었고, 그다음 문자부터 입력받은 문자열의 길이 - 1 까지 값을 확인하면 된다.

 

• 현재 가리키고 있는 문자열이 0일 경우, 이전 문자열은 1 또는 2만 가능

  : 결국 반드시 이전 문자열과 결합해야 하기 때문에 dp[i-2] 값을 그대로 갖고 온다.

 

• 현재 가리키고 있는 문자열이 0이 아닐 경우, 독립적인 문자 생성됨 + 이전 문자열과 결합이 가능한지 확인하기

  : 독립적인 문자가 생성되는 경우에는 dp[i-1] 값을 그대로 갖고 오고, 이전 문자열과 결합이 가능할 경우에는 dp[i-2] 값을 추가로 더 해줘야 한다.

 

위의 두 조건들을 고려하면 핵심 코드는 아래와 같다.

public static void solution() {
    decode();
}

public static void decode() {
    if (num.startsWith("0")) return;

    dp[0] = 1;

    for (int i = 1; i < num.length(); i++) {
        char now = num.charAt(i);
        char prev = num.charAt(i-1);

        // 0일 경우, 10 혹은 20만 가능
        if (now == '0') {
            if (prev == '1' || prev == '2') dp[i] = ((i-2 >= 0) ? dp[i-2] : 1) % 1000000;
            else break;
        }
        else {
            dp[i] = dp[i-1] % 1000000;

            // 이전 문자와 결합이 가능할 경우
            if (prev == '1' || (prev == '2' && now <= '6')) dp[i] = (i-2 >= 0) ? (dp[i] + dp[i-2]) % 1000000 : dp[i] + 1 % 1000000;
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B2011.java

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

class Main {
    static String num;
    static int[] dp;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        decode();
    }

    public static void decode() {
        if (num.startsWith("0")) return;

        dp[0] = 1;

        for (int i = 1; i < num.length(); i++) {
            char now = num.charAt(i);
            char prev = num.charAt(i-1);

            // 0일 경우, 10 혹은 20만 가능
            if (now == '0') {
                if (prev == '1' || prev == '2') dp[i] = ((i-2 >= 0) ? dp[i-2] : 1) % 1000000;
                else break;
            }
            else {
                dp[i] = dp[i-1] % 1000000;

                // 이전 문자와 결합이 가능할 경우
                if (prev == '1' || (prev == '2' && now <= '6')) dp[i] = (i-2 >= 0) ? (dp[i] + dp[i-2]) % 1000000 : dp[i] + 1 % 1000000;
            }
        }
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(dp[num.length()-1]+"");

        bw.flush();
        bw.close();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        num = br.readLine();

        dp = new int[num.length()];

        br.close();
    }
}

---

4. 결과 및 회고

현재 문자열이 0이 아닐 때, 이전 문자열과 결합이 가능한 코드를 더해주는 한 줄에서 실수를 해서 오래 걸렸던 문제였다. 조건들에서 틀리는 줄 알았는데.. ㅎ 조금 더 문제가 될 것 같은 코드를 유의해서 작성해보장.