[JAVA] 백준 2011번 【암호코드】

---

 

이 문제는 예외상황을 빠르게 캐치하는게 중요한 문제였다.

 

먼저 dp배열을 어떤 조건으로 어떤 데이터를 채울지 생각을 해봐야한다.

 

최대 5000자리 이하의 암호가 주어진다고 했으니, dp[i]에서 i는 자릿수가 될 것이고 해당 자릿수에서 만들 수 있는 경우의 수를 기록할 것이다.

 

자릿수는 높은 자릿수부터 시작할 것인데,

 

예제문제처럼 25114가 주어졌을 때,

 

dp[1] = [2] (1가지)

dp[2] = [2,5] [25] (2가지)

dp[3] = [2,5,1] [25, 1] (2가지)

dp[4] = [2, 5, 1, 1] [2, 5, 11] [25, 1, 1] [25, 11] (4가지)

dp[5] = [2, 5, 1, 1, 4] [2, 5, 1, 14] [2, 5, 11, 4] [25, 1, 1, 4] [25, 1, 14] [25, 11, 4] (6가지)

 

가 되는 것이다.

 

 

---

Case 1.

 

예제문제의 경우의 수를 따져보면서, 보이는 패턴이 있다.

 

A~Z 까지 1~26으로 표현되기 때문에,

 

1~9 사이의 숫자가 추가되는 경우, 독립적으로 알파벳을 표현할 수 있기 때문에 적어도, 이전 dp값을 그대로 갖고 온다는 사실을 알 수 있다.

 

dp[1] → dp[2] 로 가는 과정에서

 

2에다 ,5만 붙여주면 하나의 경우의 수가 생기기 때문에 2,5 경우의수를 갖게 되는 것이고

 

dp[2] → dp[3] 로 가는 과정에서

 

[2,5] [25] 경우의 수에 ,1 만 붙여주면 [2,5,1] [25,1] 경우의 수는 무조건 생긴다는 보장을 받을 수 있고

 

dp[3] → dp[4] 가정 역시

 

[2,5,1] [25,1] 경우의 수에 ,1 만 붙여주면 [2,5,1,1] [25,1,1] 경우의 수는 무조건 생긴다는 보장을 받을 수 있다.

 

마지막으로 dp[4] → dp[5] 과정에서도

 

[2, 5, 1, 1] [2, 5, 11] [25, 1, 1] [25, 11] 경우의 수에 ,4를 붙여주면 [2, 5, 1, 1, 4] [2, 5, 11, 4] [25, 1, 1, 4]  [25, 11, 4] 동일한 4개의 경우의 수가 생긴다.

 

즉, 붙는 숫자가 1에서 9 사이의 값을 가지면, dp[i+1]의 크기는 최소 dp[i]의 경우의 수를 포함하기때문에 

 

dp[i+1] = dp[i] 로 표현할 수 있다.

 

여기서 주의해야할 사항은 0이 붙었을 때이다.

 

0은 1~9와 다르게 독립적으로 [2,5,0] 과 같이 혼자 쓰일 수 없기 때문에, 1에서 9사이의 숫자가 뒤에 붙었을때에만 

 

dp[i+1] = dp[i] 로 표현할 수 있다.

 

 

---

Case 2.

 

dp[3] → dp[4] 과정에서는 2개에서 4개로 늘어났고, dp[4] → dp[5] 과정에서는 4개에서 6개로 늘어났다.

 

dp[3] → dp[4] 상황을 먼저 살펴보면 Case 1. 에서 살펴봤듯이 생기는 2개의 경우의수에 또다른 2개의 경우의 수가 발생했다.

 

[2,5,1] [25, 1] 의 경우의 수에 1이 붙는경우 독립적으로 붙이는 것이 아니라 합쳐서 11로 표현할 수 있어  [2, 5, 11] [25, 11] 와 같은 새로운 경우의 수가 생긴다. 

 

즉 뒤에 붙는 숫자가 합쳐져서 10~ 26 값을 만들어내면 새로운 알파벳 하나로 표현할 수 있기 때문에 새로운 경우의 수가 생기는 것이다.

 

결론부터 말하면, 위와 같은 경우에는 Case 1. 에서 구했던 dp[i+1] = dp[i] 상황에서 dp[i+1] 에 dp[i-1] 값을 한번 더 더할 수 있다.

 

dp[3] → dp[4] 과정에서 

 

11이 만들어지고 이는 알파벳 하나를 표현할 수 있다.

 

즉. [2,5] [25] 상황에서 11을 붙인다고 생각하면 [2,5 ,11] [25 ,11] 이 되는 것이다.

 

그리고 [2,5] 와 [25] 는 dp[2]의 경우의 수와 같다.

 

마지막으로, dp[4] → dp[5] 과정을 살펴보면 

 

1뒤에 4가 붙기 때문에, 이 경우 역시 14로서 하나의 독립적인 알파벳으로 만들 수 있다.

 

즉 dp[3] 경우의 수인 [2,5,1] [25, 1] 에서 ,14 를 붙여주는 것과 같아지는 것이다.

 

[2,5,1, 14] [25,1,14] 의 경우의 수가 Case 2.와 같은 상황때문에 생기게 되는 것이다.

 

 

---

또한 제일 첫번째 자릿수가 0으로 시작하는 경우는 어떤 알파벳으로도 해독 될 수 없기 때문에 오류로 판단하고 0 값을 출력하면 된다.

 

 

 

 

결론은

 

1. Case 1.의 이유로 뒤에 붙는 숫자가 0이 아닌 1~9 값이라면 최소 이전 dp값의 경우의 수를 갖을 수 있게 된다.

2. Case 2.의 이유로 뒤에 붙는 숫자를 합쳐서 10~26을 만들 수 있다면, dp[i]는 dp[i-2]의 경우의 수에 10~26사이의 독립적인 알파벳을 붙인 꼴이 되기 때문에 dp[i-2]의 경우의 수를 가져올 수 있다.

3. 0으로 시작하는 수는 알파벳으로 표현할 수 없으므로 0값을 리턴한다.

 

위 세가지를 코드로서 구현하면 정답을 맞출 수 있다!

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		long[] dp = new long[input.length()+1];
		
		dp[0] =1;
		dp[1] = 1; // 0인 경우 제외하면 무조건 1개
		
		if (input.charAt(0) == '0') {
			System.out.println(0);
			return;
		}
		
		
		for (int i = 1; i < input.length(); i++) {
			char front = input.charAt(i-1); //앞 숫자
			char back = input.charAt(i);
			int num = (front-'0')*10+(back-'0'); //숫자를 합쳤을 때
            
			if(back>='1' && back<='9') {//Case 1
				dp[i+1]=dp[i];
				 dp[i+1]%=1000000; 
			}
            
			if((num>=10 && num<=26)) { //Case 2
				dp[i+1]+=dp[i-1];
				 dp[i+1]%=1000000; 
			}
		}
		System.out.println(dp[input.length()]%1000000);
	}

}