[Python] 백준 2011번: 암호코드 풀이

 

 

소스코드

n = list(map(int,input()))
l = len(n)
dp = [0 for _ in range(l+1)]
if (n[0] == 0) :
    print("0")
else :
    n = [0] + n
    dp[0]=dp[1]=1
    for i in range(2, l+1):
        if n[i] > 0:
            dp[i] += dp[i-1]
        temp = n[i-1] * 10 + n[i]
        if temp >= 10 and temp <= 26 :
            dp[i] += dp[i-2]
    print(dp[l] % 1000000)
    

 

 

요새 풀었던 문제 중 가장 어려웠던 문제... ㅜㅜ 나는 왤케 이해력이 느릴까... 이런 문제를 풀 때마다 자책감이 든다...큐ㅠㅠㅠ

 

아무튼 풀이를 시작해보자.

 

25114 같은 숫자에서 각 자리수 또는 두 자리수를 알파벳으로 치환시켜 암호를 해독하는 문제이다.

알파벳은 26자리 이므로 A:1 부터 Z:26까지 의 숫자를 가질 수 있다.

 

즉 1~26 범위의 숫자만 알파벳으로 치환이 가능한 것이다.

 

* 그리고 한자리수 0은 해독할 수 없으므로 10이나 20만 알파벳으로 처리할 수 있다.

 

이 문제 또한 작은 문제에서부터 큰 문제로 접근해가는 상향식 접근법으로 풀 것이다.

n = 25114 같은 숫자가 주어진다면 1번 인덱스 '2' 부터 차례로 몇 개의 암호 가짓수를 가지는지 계산하면 된다.

 

방법은 이러하다.

 

1) 현재 자리숫자가 0 보다 클 때 -> 이전 dp 값을 더한다. ( 이전 dp 가 가지는 방법들 뒤에 한 자리수로 추가하기만 하면 되므로 이전 dp값을 default로 가질 수 있다. )

예) 2 5 1 1 4 에서 빨강색까지는 이미 구했다고 하자. 2  5  1  1 / 25  1  1 / 2  5  11 / 25  11 이렇게 4가지의 방법 뒤에 4를 독립적으로(한자리수로 생각) 붙힐 수 있으므로 4가지를 더할 수 있다.

 

2) 이전 자리수와 현재 자리수를 두 자리숫자로 볼 때 10~26사이의 숫자에 해당할 때 -> 전 전 dp 값을 더한다. 

예) 2 5 1 1 4 에서 빨강색까지의 방법 -> 2  5  1 / 25  1 에다가 독립적으로 14를 붙힐 수 있으므로 2 가지를 더할 수 있다.

 

이렇게 두 가지 조건문을 달면 된다.

그리고 처음 숫자가 0으로 시작하는 것은 10, 20으로도 만들 수 없으므로 아예 0으로 출력해주는 예외를 추가해주면 된다.