[Java] 백준 2011번 - 암호코드

[문제]

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

2011번: 암호코드

[풀이]

DP를 사용하여 풀이하는 문제로, 해당 블로그를 참고해서 풀이를 진행하였습니다.

https://happybplus.tistory.com/45

[백준, BOJ 2011] 암호코드 (java)

숫자가 만들어질 수 있는 조건을 생각하고 각 조건별로 처리를 다르게 해주었습니다.

 

 

우선, 맨 처음 숫자가 0이면(numbers.charAt(0)이 0일때) 해석이 불가능합니다.

 

또한 맨 처음 숫자가 0이 아니고, 현재 숫자가 0이라면(numbers.charAt(i)) 이전 숫자에 1 또는 2가 있을 경우에만 10, 20으로 처리가 가능합니다. 만약, 1 또는 2가 없다면 해석이 불가능합니다.

 

마지막으로 맨 처음 숫자가 0이 아니고, 또한 현재 숫자도 0이 아니라면 현재 index의 이전숫자(numbers.charAt(i-1))의 값에 따라 3가지 경우의 수가 있습니다.

• 이전 숫자가 1이라면 dp[i] = dp[i-1] + dp[i-2]
• 이전 숫자가 2라면 현재 숫자가 1 ~ 6 일때만 26보다 작으므로 dp[i] = dp[i-1] + dp[i-1];
• 위의 경우를 제외한 숫자들은 모두 단독처리 대상이므로 dp[i] = dp[i-1];

이때, 만약 현재 index가 1이라면, dp[i-2]대신 1을 더해줍니다.

 

 

예제1을 예시로 설명해보자면,

숫자들이 2 5 1 1 4 가 들어옴.

0 -> 2
1 -> 25 2+5
2 -> 25+1, 2+5+1
3 -> 25+11, 2+5+11, 25+1+1, 2+5+1+1
4 -> 25+11+4 2+5+11+4, 25+1+1+4, 2+5+1+1+4,25+1+14, 2+5+1+14

0번째 index의 값은 2 이므로, dp[0] = 1입니다.

1번째 index의 이전 값은 2 이므로 dp[1] = 2입니다.

2번째 index의 이전값은 5이므로, 단독처리 대상이라 25와 2+5에 각각 1을 단독으로 더해 dp[2] = 2가 됩니다.

3번째 index의 이전값은 1이므로, index-2의 값들과도 결합이 가능합니다. 따라서 25와 2+5에 각각 11을 더한 코드와 25+1과 2+5+1에 단독으로 1을 더한 코드 총 4가지가 가능합니다. (dp[3] = dp[2] + dp[1] = 4)

4번째 index는 이전값을 1로 가지고 있으므로, 3번과 같이 dp[4] = dp[3] + dp[2] = 6이 됩니다.

 

따라서 가능한 모든 방법은 6가지로 dp[4]를 통해 알 수 있습니다. 

[코드]

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

public class Main {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String numbers = br.readLine();
        N = numbers.length();
        int[] dp = new int[N];
        decode(numbers, dp);
        System.out.println(dp[N-1]);
    }
    public static void decode(String numbers, int[] dp) {
        if(numbers.charAt(0) == '0') {
            // 첫번째 숫자가 0이면 해석 불가능
            return;
        }
        dp[0] = 1;
        for(int i=1;i<numbers.length();i++) {
            // numbers[i]가 0일때는 앞자리가 1 || 2일때만 해석이 가능함
            // 무조건 numbers[i-1]과 numbers[i]가 한 세트이므로, dp[i-2]랑 같은값.
            if(numbers.charAt(i) == '0') {
                if(numbers.charAt(i-1) != '1' && numbers.charAt(i-1) != '2') {
                    // 잘못된 코드임
                    return;
                }
                if(i == 1) {
                    dp[i] = 1;
                } else {
                    dp[i] = (dp[i] + dp[i-2])%1000000;
                }
            } else {
                // 이전 숫자가 1인 경우
                if(numbers.charAt(i-1) == '1') {
                    if(i == 1) {
                        dp[i] = (dp[i-1] + 1)%1000000;
                    } else {
                        dp[i] = (dp[i-1] + dp[i-2])%1000000;
                    }
                } else if(numbers.charAt(i-1) == '2' && numbers.charAt(i) >= '1' && numbers.charAt(i) <= '6') {
                    if(i == 1) {
                        dp[i] = (dp[i-1] + 1)%1000000;
                    } else {
                        dp[i] = (dp[i-1] + dp[i-2])%1000000;
                    }
                } else {
                    // 무저건 단독으로 처리
                    dp[i] = dp[i-1];
                }
            }
        }
    }
}