[BOJ/python3] 2011번 암호코드

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

2011번: 암호코드

---

문제

A를 1, B를 2, ... ,Z를 26이라 하자.

BEAN -> 25114 로 변환된다.

25114 를 문자로 다시 변환하려면  "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 의 6가지의 경우가 나온다.

 

어떤 암호가 주어졌을 때, 그 암호 해석이 몇 가지 나올 수 있는지 구하는 프로그램

풀이

완전 DP문제이다.

현재 위치를 i라 하면, int(str(dp[i-1]) + str(dp[i]))  이 26 이하인지 확인하면 된다. 만약 해당 숫자가 26 이하이면 dp[i]=dp[i-1]+dp[i-2] 이고, 26 이상이면 dp[i]=dp[i-1] 이다.

틀렸어...

라고.....생각했는데 전혀 아니었다.

잘못 이해한 사람의 험난한 여정

무시하고 넘어간 문장이 있다.

1. 마지막 결과값에 %1000000 

2. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력

 

암호가 잘못 될 수도 있다는 뜻... -> 즉 1203 이면 12/0(무시)/3 으로 해석하는게 아니라 무조건 1/20/3 으로만 가능하단거. 문장에서 0을 무시할 수 있다는 말은 어디에도 없었다.

 

이 경우 풀이가 많이 달라진다.

0과 지금 쌍, 지난 쌍 까지 고려해서 문제를 풀어야 한다...

 

암호를 s,  s[:i] 일 때의 경우의 수를 dp[i]라 하자.

그리고 i번째 숫자를 조사한다 할 때

- 현재 위치의 두자리 숫자(int(s[i-1]+s[i]))를 num

- 바로 앞선 두자리 숫자를(int(s[i-2]+s[i-1]))를 last_num 이라 하자

 

1. 첫번째에 0이 오는 경우 return 0

2. 0이 연속 2회 이상 나오는 경우 return 0

3. s[i]가 0인 경우

     3-1.  s[i-1]이 3 이상인 경우 return 0

     3-2.  s[i-1]이 2 이하이면서, s[i-2]가 0인 경우 dp[i]=dp[i-1] 

     3-2.  last_num이 26보다 큰 경우 dp[i]=dp[i-1]

4. s[i]가 0이 아닌 경우

     4-1. i-1이 0인 경우 dp[i]=dp[i-1]

     4-2. num이 26보다 큰 경우 dp[i]=dp[i-1]

     4-3. 위 경우 둘 다 아닌 경우 dp[i]=dp[i-1]+dp[i-2]

 

이 조건을 생각하는게 너무 어려웠다

 

소스코드

def answer(s):
    if s[0] == '0':
        return 0
    if len(s) == 1:
        return 1
    
    dp = [0]*(len(s)+1)
    dp[0] = 1
    if s[1] == '0' and int(s[:2]) > 26:
        return 0
    elif( s[1] == '0' and int(s[:2]) <= 26) or int(s[:2]) > 26:
        dp[1] = 1
    else:
        dp[1] = 2
    
    for i in range(2, len(s)):
        num = int(s[i-1]+s[i])
        last_num = int(s[i-2]+s[i-1])
        
        if (s[i] == '0' and num > 26)\
            or (s[i] =='0' and s[i-1] == '0'):
            return 0
        if s[i] == '0':
            if dp[i-1] == 0 or s[i-2] == '0' or last_num > 26 :
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-2]
        else:
            if num > 26 or s[i-1] == '0':
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1] + dp[i-2]
    
    return dp[len(s)-1]%1000000

s = input()
print(answer(s))