백준 2011. 암호코드

tose33 2022. 8. 1. 15:33

2011번: 암호코드

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

www.acmicpc.net

알파뱃은 총 1~26으로 표현 가능하기 때문에 최대 두자리 까지만 체크해야 한다.

d[i][0] : 마지막 자리가 한자리로 끝나는 경우 (예: 2/5, 2/5/1, 2/5/10/5 ... )

d[i][1] : 마지막 자리가 두자리로 끝나는 경우 (예: 25, 2/5/10, 25/10 ... )

점화식:

(현재 자리가 0이 아닐때) d[i][0] = d[i-1][0] + d[i-1][1]

(이전자리와 현재자리를 합한 두자리수가 1~26 이내라면) d[i][1] = d[i-1][0]

d[i][0]의 조건이 현재 자리가 0이 아닐때인 이유는, 현재 자리가 0이라면 2/5/1/0 이런 식으로 마지막 한자리가 0이라는 뜻인데 알파뱃 범위는 1~26까지 이므로 불가능하다.