백준 2011 암호코드 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/2011

2011번: 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

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

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제다.

암호가 잘못되어 암호를 해석할 수 없는 경우가 있나? 생각했는데 0이 있었다.

만약 101이 입력으로 들어온다면

10 + 1로 한 가지 암호만 존재한다.

01이나 

07

001 등의 입력은 모두 잘못된 암호로 0을 출력해야 한다.

우선 dp 점화식은

현재 검사하는 숫자가 '1'일때,

1번 점화식 : dp[i] = dp[i] + dp[i-1]

현재 검사하는 숫자가 '21'로 두 자리 숫자이면서 26 이하일 때

2번 점화식 : dp[i] = dp[i] + dp[i-2]

 

여기에 0이 오는 경우를 고려해야 한다.

만약 현재 숫자가 0인 경우 앞의 숫자와 합쳐 1~26 범위에 들어오는지 확인해야 한다.

20인 경우 2번 점화식을 실행하고,

범위에 들어오지 않는다면 잘못된 암호이므로 더하지 않는다.

 

현재 숫자가 0이 아닌 경우는 1번 점화식을 무조건 실행하고, 조건에 따라 2번 점화식을 수행하면 된다.

 

110025114의 경우 0을 출력해야 하고

11025114의 경우 6을 출력해야 한다.

즉, 아예 00처럼 변환 불가능한 숫자가 중간에 껴있다면 뒷부분이 어쨌든 그냥 0이 출력되도록 해야 한다.

코드

val br = System.`in`.bufferedReader()
const val MOD = 1000000
fun main() = with(System.out.bufferedWriter()) {

    br.readLine().let{
        if(it[0]=='0'){
            write("0")
            close()
            return@with
        }
        val dp = LongArray(it.length + 1)
        dp[0] = 1
        dp[1] = 1
        for (i in 2 until dp.size) {
            if(it[i-1]=='0'){
                if(it.substring(i-2,i).toInt() in 1.. 26){
                    dp[i] +=dp[i - 2]
                    dp[i] = dp[i] % MOD
                }
            }
            else{
                dp[i] = dp[i - 1]
                dp[i] = dp[i] % MOD
                if (it.substring(i - 2, i).toInt() in 11..26) {
                    dp[i] += dp[i - 2]
                    dp[i] = dp[i] % MOD
                }
            }
        }
        write("${dp[dp.size-1]}")
    }
    close()
}