백준 2011번

2011번: 암호코드

알파벳 A-Z 순서대로 1~26까지 번호를 매긴 뒤 숫자로 되어있는 암호문이 입력되었을 때 

암호문의 해독 가짓수가 몇가지 인지 파악하는 DP 관련 문제이다.

---

 

풀이

arr

1

2

1

2

3

4

5

6

12123456이라는 숫자가 입력되었을 때 경우의 수를 따져보고 점화식을 유추하고자 한다.

 

숫자	경우의수	경우의 수 갯수
1	{1}	1
12	{1,2}, {12}	2
121	{1,2,1}, {12, 1}, {1, 21}	3
1212	{1,2,1,2}, {12,12}, {12, 1,2} {1, 21, 2}, {1,2,12},	5
12123	{1,2,1,2,3}, {12, 1,2,3}, {12, 12, 3} {1,21,2,3}, {1, 21, 23}, {1,2,12,3} {1,2,1,23}, {12,1,23}	8
121234	{1,2,1,2,3,4}, {12, 1,2,3,4}, {12,12,3,4} {1, 21, 2, 3, 4}, {1, 21, 23, 4}, {1,2,12,3,4} {1,2,1,23,4}, {12,1,23,4}	8
1212345	{1,2,1,2,3,4,5}, {12, 1,2,3,4,5}, {12,12,3,4,5}, {1, 21, 2, 3, 4,5}, {1, 21, 23, 4,5}, {1,2,12,3,4,5} {1,2,1,23,4,5}, {12,1,23,4,5}	8
12123456	{1,2,1,2,3,4,5,6}, {12, 1,2,3,4,5,6}, {12,12,3,4,5,6}, {1, 21, 2, 3, 4,5,6}, {1, 21, 23, 4,5,6}, {1,2,12,3,4,5,6} {1,2,1,23,4,5,6}, {12,1,23,4,5,6}	8

 

12123까지 입력하였을때는 경우의 수 개수가 dp [n] = dp [n-1] + dp [n-2] 형태로 증가하다가

121234가 입력되고 나서 부터는 경우의 수가 더 이상 증가하지 않은 것을 확인할 수 있다. 새로운 경우의 수가 추가되려면 해독 범위 내에 숫자인 1~26 내에 존재해야 하는데 34라는 숫자는 범위 밖에 존재하기 때문에 경우의 수가 증가하지 않은 것이다.

여기까지 표를 이용해 점화식을 유추해보면 (arr [n-1]*10) + arr [n] > 26이 되면 해독 가능한 경우의 수가 증가할 수가 없다.

따라서 (arr[n-1]*10) + arr [n] > 26 일 경우 dp [n] = dp [n-1]의 값이 된다는 것을 유추할 수 있다.

 

 

0이 입력되었을 경우.

arr	1	2	0	2
dp	1	2	1	2

0도 입력될 수 있기 때문에 0이 입력 되었을때 경우의 수를 구할 수 있도록 해줘야 한다.

12까지 입력 되었을때는 앞서 찾아본 규칙을 이용해 2가지 해독이 가능하다는 것을 알 수가 있다.

120이 입력 되었을 때는 가능한 경우의 수는 {1, 20}만 가능하다. 

그러면 점화식을 유추 해보면 arr [n] == 0 이면 dp [n] = dp [n] -1의 점화식을 유추할 수가 있다.

 

점화식을 정리해보면 다음과 같다

(arr [n-1] * 10) + arr [n] > 26 일 경우 dp [n] = dp [n-1]

arr [n] == 0 일 경우 dp [n] = dp [n-1] -1

그 외에 경우 dp [n] = dp [n-1] + 1

 

코드

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String word = sc.next();
        int n = word.length()+1;
        long mod = 1000000;

        long [] dp = new long[n];
        dp[0] = 1;
        for(int i = 1; i<n;++i)
        {
            int x = word.charAt(i-1) - 48;
            if(x>=1 && x <= 9)
            {
                dp[i] = (dp[i] +  dp[i-1]) % mod;
            }
            if(i==1)
            {
                continue;
            }

            int t = word.charAt(i-2) - 48;
            int tempCount = (t*10)+x;
            if(t==0)
            {
                continue;
            } else if (tempCount >= 10 && tempCount <=26) {
                dp[i] = (dp[i] + dp[i-2]) % mod;
            }
        }

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

}