백준2011(파이썬) - 암호 코드

https://www.acmicpc.net/problem/2011

2011번: 암호코드

• 이 문제는 처음에는 한 자리수와 두 자리수의 경우의 수를 모두 따져서 생각했었다. 하지만 그렇게 되면 반복되는 숫자들이 너무 많아져서 생각하다가 DP로 구현을 시도했다.
• 먼저 DP 테이블을 만들어주고, 앞에서 부터 for문으로 하나씩 확인해준다.
• 현재 숫자와 바로 그 앞자리 숫자가 10이상 26이하 일때는 두자리가 가능한 숫자이기 때문에 앞자리 숫자 앞의 DP[현재숫자인덱스 - 2]에 저장되어있는 값을 DP[현재숫자]에 넣어주고, 현재 숫자는 1부터 9 까지의 숫자 중 하나일 것이기 때문에 앞자리 숫자의 DP[앞자리숫자] 또한 DP[현재숫자]에 넣어준다.
• 두 가지 경우를 모두 생각해주고 더해준뒤, 1000000으로 나눈 값을 DP[현재숫자] 의 최종 값이라고 생각하면된다.
• 위 과정을 for문으로 반복해주면, DP테이블에서 (입력된 숫자의 길이)인덱스를 가진 값을 출력해주면 된다.

import sys
input = sys.stdin.readline

data = list(map(int,input().rstrip()))
len_data = len(data)
dp = [0] * (len_data+1)
if data[0] == 0:
    print(0)
    exit(0)
else:
    # 인덱스맞추기 위한 0 삽입
    data = [0] + data
    # 1까지는 만들 수 있는 글자 1개
    dp[0] = 1
    dp[1] = 1
    for i in range(2,len_data+1):
        # 앞자리숫자와 그 다음 숫자가 26이하의 두자리 숫자라고 가정
        if 10 <= data[i-1]*10 + data[i] <= 26:
            # i번째 dp에 앞앞 자리 까지의 dp값을 더해준다. -> 두자리숫자 한개로 친다.
            dp[i] += dp[i-2]
        # 한자리 숫자라고 가정
        if 1 <= data[i] <= 9:
            # 하나 앞자리 숫자의 dp값을 더해준다.
            dp[i] += dp[i-1]
        dp[i] %= 1000000
print(dp[len_data])