728x90
2011번: 암호코드
나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.
www.acmicpc.net
분석
- 10 ≤ 현재 숫자와 바로 그 앞자리 숫자 ≤ 26일 때, 두자리가 가능한 숫자
- dp[i] += dp[i-2] : 앞자리 숫자 앞의 DP[현재숫자인덱스-2]에 저장되어있는 값을 DP[현재숫자]에 넣어줌
- 1 ≤ 현재 숫자 ≤ 9
- dp[i] += dp[i-1] : 앞자리 숫자의 DP[앞자리숫자] 또한 DP[현재숫자]에 넣어줌
풀이
code = list(map(int, input()))
n = len(code)
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
if code[0] == 0:
print(0)
else:
for k in range(1, n):
i=k+1
# 1자리
if code[k] > 0:
dp[i] += dp[i-1]
# 2자리
if 10 <= code[k]+code[k-1]*10 <= 26:
dp[i] += dp[i-2]
print(dp[n] % 1000000)
728x90