BOJ 2011 Alphacode

알파벳 대문자('A' ~ 'Z')로 이루어진 단어 'A'는 1로, 'B'는 2로, ... , 'Z'는 26으로 변환한 암호 코드는 여러가지 알파벳의 조합으로 해석될 수 있다.

숫자 1 ~ 26으로 변환한 암호 코드가 주어질 때, 암호의 해석이 몇 가지 나올 수 있는지 구하는 문제이다.

dp이다. d[n] = n번째 숫자까지 봤을 때, 해석될 수 있는 경우의 수
1에서 26까지의 숫자만 알파벳으로 변환될 수 있으므로, n-1, n번째 숫자 2개를 보고 경우의 수가 어떻게 구성될지 판단할 수 있다.

n-1, n번째 숫자 2개가 1보다 크고 26이하인 경우 두 자리 숫자인 경우 두 자리 숫자를 하나의 알파벳으로 바꾸거나, 그냥 맨 끝 하나의 숫자만 알파벳으로 바꾸는 두 가지 경우가 있어서 d[n]=d[n-2]+d[n-1]이 될 것인데, 10이나, 20, 01, 02 같은 경우를 조심해야 한다. 10, 20인 경우는 무조건 10, 20 이렇게 한 가지로 밖에 해석이 안되므로 d[n]=d[n-2], 01, 02같은 경우도 앞의 0(n-1번째 자리)은 무조건 n-2번째 자리의 수와 함께 쓰여야 하므로(10, 20 이런식으로) 1, 2, 이렇게 한 가지 경우로만 해석된다. 즉 d[n]=d[n-1] 이 될 것이다.

그리고 n-1, n번째 숫자 2개가 26보다 클 경우에는 맨 뒤 한 자리만 알파벳으로 변환 가능하므로 d[n]=d[n-1]이 될 것이다.

그리고 경우의 수가 커질 수 있으므로 중간 중간 modulo를 해줘야하는 것도 잊지 말아야 한다.

---------------------------------------------------------------------------
재채점 후 WA를 받아서, 다시 풀어보는 중이다. 예전에 풀었던 방식이랑 같지만 다시 해보니 코드가 좀 더 깔끔해지는 것 같다.
d[n] = n번째 숫자를 끝으로 하는 나올 수 있는 해석의 가짓수
n-1번째, n번째 숫자 2개를 보고 결정하는데, 이번에 좀 다르게 한 것은 d[0]은 무조건 1일 테고, d[1]값은 경우에 따라 1일 수도, 2일 수도 있는데.. 물론 저번에 풀었던 방식은 d[len]을 구하고, 이번에 푸는 방식은 d[len-1]을 구하는 방식이라... 저번에 풀었던 방식도 틀린 것은 아닌 것 같은데... 여튼 d[len-1]을 구하는 방식으로 하니까 더 쉬운 것 같다.

그리고 제출했는데, 90퍼센트를 넘어서 WA를 받았다. 내가 알기로 BOJ 데이터가 보통 큰 데이터부터 작은 데이터 순으로 채점을 하기 때문에, 아마 내가 틀린 것은 작은 케이스에 대해서 인 듯한데, 생각해보니 문제에 꼭 올바른 케이스, 즉 반드시 해석 가능한 케이스가 들어온다는 말이 없다.
그래서 d[0]에는 무조건 1을 넣으면 안될 것이라는 생각이 들었다. 만약 맨 처음에 0이 들어오면 0으로 초기화 해줘야 한다... 아니 그냥 맨 처음이 0이면 무조건 경우의 수는 0이므로 예외처리 해서 0을 출력해주면 될 것 같다. 역시 불가능한 경우가 들어오는 것이 문제였다. AC를 받았다.