[알고리즘] 암호코드
난이도
Gold 5
문제
상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.
- 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
- 선영: 그럼 안돼. 만약, “BEAN”을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
- 상근: 그렇네. 25114를 다시 영어로 바꾸면, “BEAAD”, “YAAD”, “YAN”, “YKD”, “BEKD”, “BEAN” 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
- 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
- 상근: 얼마나 많은데?
- 선영: 구해보자! 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.
출력
나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.
암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.
예제 입력
25114
예제 출력
6
해설
쉬운 DP문제인 줄 알고 들이댔다가 시간을 많이 썼다. 기본적인 구현 자체는 금방 할 수 있는데, ‘0’을 처리하는 과정이 조금 복잡하다. 쉬운 예로는 1001 = 0부터, 1090 = 0이나 120 = 1 등의 사례를 모두 체크할 수 있어야 하기 때문이다. 구현해놓은 코드에 예외처리하여 살을 붙였더니 코드가 굉장히 난잡해졌다. 출력값으로 0이 나올 수 있는 케이스와 0이 입력되었을 때 어떻게 동작해야되는지를 깊게 생각해보고 다시 코드를 짜면 보다 깔끔하게 구현할 수 있을 것 같다.
제출 코드
cText = input().strip()
n = len(cText)
d = [0 for i in range(n)] #ind만큼 읽었을 때 발생가능한 가짓수
if('00' in cText):
print(0)
exit()
def validTest(a,b): #숫자 ab가 들어왔을 때 몇 개로 해석 가능한지?
ret = 0
if(a== '0' or b == '0') :
return 1
if(int(a) < 2):
ret = 2
elif(int(a) == 2 and int(b) <= 6):
ret = 2
else:
ret = 1
return ret
for i in range(n):
if(cText[i] == '0'):
if(i == 0):
print(0)
exit()
elif(int(cText[i-1])>=3):
print(0)
exit()
#print(d)
if(i == 0):
d[i] = 1
elif(i == 1):
d[i] = validTest(cText[0],cText[1])
else:
#d[i] = d[i-1] 그리고 조건이 되면 d[i-2]
a = cText[i-1]
b = cText[i]
if(cText[i] == '0'):
d[i] = d[i-2] %1000000
elif(validTest(a,b) == 2):
d[i] = (d[i-1] + d[i-2]) % 1000000
else:
d[i] =(d[i-1]) % 1000000
#print(d)
print(d[n-1])