[BOJ 2011] 암호코드

문제 링크 : https://www.acmicpc.net/problem/2011

본문

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

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

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

입력

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

출력

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

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

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

문제에서 사용할 알고리즘에 대한 힌트를 주고 있다. 길이가 $5000$글자까지인데, 정답이 매우 클 수 있으므로 나머지 연산 후 답을 출력하라는 조건이 있다. 이 경우 거의 무조건 다이나믹 프로그래밍을 사용한다. 그럼 문제를 어떻게 쪼갤 수 있을지 생각해보자.

DP 알고리즘을 설계하기 위해서는 몇 가지 요소가 필요하다.

• dp[i]를 i번째 글자부터의 정답이라고 선언하자. 그럼 문제의 정답은 dp[0]을 출력해주면 될 것이다
  • 종료 지점이 제일 앞이므로, Top-Down 방식을 사용하도록 하자

• 시작 지점은 dp[strlen()] = 1로 설정한다. 문자열의 끝에서는 비어있는 문자열 1가지만 존재하기 때문

• 점화식은 현재 위치에 가능한 글자의 개수에 따라 정해진다. 아래는 가능한 case들에 대한 설명이다
  • str[i] == 0인 경우 :: $0$은 단독으로 알파벳으로 변환될 수 없는 값이며, 앞에 반드시 $1$ 또는 $2$가 존재해야한다
    • 만약 아니라면, 이 암호문은 해석할 수 없는 암호문이라고 판단할 수 있다
  • str[i] == 1인 경우 :: $1$을 A로 대응시키거나, 뒤의 숫자과 결합시켜 J ~ S로 대응시킬 수 있다
    • 뒤의 숫자는 어떤 것이 오더라도 상관없다 (J == 10, S == 19)
    • 두 가지 경우 모두 적절한 암호문을 만들 수 있으므로, dp[i] = dp[i + 1] + dp[i + 2]로 계산할 수 있다
  • str[i] == 2인 경우 :: $2$를 B로 대응시키거나, 뒤의 숫자와 결합시켜 T~Z로 대응시킬 수 있다
    • 뒤의 숫자는 $0$ ~ $6$까지 가능하다 (T == 20, Z == 26)
    • 뒤의 숫자가 이 범위 내에 있다면 dp[i] = dp[i + 1] + dp[i + 2]로 계산할 수 있다
    • 만약 아니라면 $2$를 B로 대응시킨 경우만 가능하므로 dp[i] = dp[i + 1]로 계산해야한다
  • 나머지 경우 :: $3$ ~ $9$ 범위까지 있을텐데, 각각 1가지의 알파벳으로밖에 대응시킬 수 없다 (C == 3, I == 9)
    • 현재 위치의 알파벳은 고정되므로 정답에 영향을 주지 못한다. 고로 dp[i] = dp[i + 1]로 계산해야한다

이렇게 DP 알고리즘을 설계하여 그대로 구현하기만 하면 된다.

소스코드

Github Link : Source Code

참고 알고리즘 : 다이나믹 프로그래밍