[BOJ] 2011 - 암호코드 (Python)

 

 

아이디어

 

동적 계획법으로 암호를 구성하는 숫자들이 직전의 숫자와 붙을 수 있는지 여부를 확인하여 가짓수를 구한다.

 

 

풀이

 

10과 20을 제외하고 0으로 시작하거나 30처럼 0이 포함된 암호는 해석할 수 없으므로 0을 출력한다.

elif문에서 0이 아니면서 N의 길이가 1인 암호는 1을 출력한다.

그 외의 경우는 1로 채워진 N+1 길이의 리스트 dp를 생성하고, for문에서 암호를 구성하는 숫자들을 차례로 확인한다.

 

만약 현재 숫자가 0인 경우 직전 숫자와 붙여야 하므로 앞의 숫자 이전의 경우로 되돌린다.

직전 숫자가 0이 아니면서 현재 숫자를 직전 숫자와 붙일 수 있으면 직전 숫자까지의 가짓수와 그 이전 가짓수를 더한다.

그 외에 직전 숫자와 붙일 수 없는 경우는 직전 숫자까지의 가짓수로 저장한다.

 

code = input()
N = len(code)
if code.count('10')+code.count('20') != code.count('0'):
    print(0)
elif N <= 1:
    print(1)
else:
    dp = [1]*(N+1)
    for i in range(1, N):
        dp[i+1] = dp[i]
        if code[i] == '0':
            dp[i+1] = dp[i-1]
        elif code[i-1] != '0' and int(code[i-1:i+1]) <= 26:
            dp[i+1] += dp[i-1]
    print(dp[-1]%1000000)