[BOJ-2011] 암호코드

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

2011번: 암호코드

---

[주저리 & 풀이]

알고보면 간단한데, 약간 생각이 필요한 문제이다.

dp 유형들은 알면간단한데, 그 과정까지가 조금 머리 아프다 ㅠㅠ

 

(1) 암호해독 불가능 경우 (0리턴)

입력란의 비밀번호가 5000이하의 자연수이기때문에

비밀번호가 없거나, 첫번째 숫자가 0이면, 암호를 해독할 수 없다.

왜냐하면, 0번째에 대응하는 문자가 없기때문이다.

(1부터 시작하고, 1은 'A'를 의미한다)

 

그리고 덤으로 암호의 최대길이는 5000이기때문에

인덱스 혼란을 막기위해서 DP배열과, PW배열(비밀번호숫자)의 길이를 5001로했다.

 

 

(2) 현재 숫자가 1~9 일때

여기가 dp를 활용해야한다.

몇가지 예를 다뤄보고 감을 잡아보자

 

(예) 암호가 21154 일때

* 1번째 자리 암호숫자: 2 *

만들수 있는 암호: B

문자 한개로 만들 수 있는 암호는 B 밖에없다.

DP[1]= 1 

 

---

* 2번째 자리 암호숫자: 1 *

현재 2번째 해당하는 숫자는 0이 아닌 1~9 사이의 숫자이다.

그러면 아래의 두가지 경우를 생각해봐야한다. 

"이전에 만든 암호에 현재암호를 붙이는 경우"와 "새로운 알파벳문자로 암호를 만드는 경우"가 있다.

 

- 이전에 만든 암호에 현재 암호를 붙이는 경우(1='A')

이전암호[B]+ 현재암호[A] => [BA]

 

- 새로운 알파벳문자로 암호를 만드는 경우

1번째 숫자: 1  /   2번째 숫자: 2 => (1x10)+2 =12 =>[L]

 

바로 이전의 숫자x10 + 현재숫자 의 결과가 10~26 사이라면, J~Z 사이의 알파벳으로 변환 할 수 있다.

이를 식으로 변환하면, PW[i-1]*10+PW[i] 이다.

따라서 만들수 있는 암호는 [BA, L] 이므로, DP[2]= 2 

 

---

* 3번째 자리 암호 숫자: 1 *

- 이전에 만든 암호에 현재 암호를 붙이는 경우(1='A')

[BA]+[A] => [BAA]

[L]+[A] => [LA]

 

- 새로운 알파벳 문자로 암호를 만드는 경우

2번째 숫자: 1 / 3번째 숫자: 1 => (1x10)+1=11 =>[K]

1번째에서 만든문자열[B] + [K] =>  [BK]

 

따라서 만들 수 있는 암호는 [BAA, LA, BK] 이다. DP[3]=3

---

* 4번째 자리 암호 숫자: 5 *

- 이전에 만든 암호에 현재 암호를 붙이는 경우(5='E')

[BAA]+[E] =>[BAAE]

[LA]+[E] =>[LAE]

[BK]+[E] =>[BKE]

 

- 새로운 알파벳 문자로 암호를 만드는 경우

3번째 숫자: 1 / 4번째 숫자: 5 => 15 => O

2번째에서 만든 문자열[BA, L] +[O] => [BAO, LO]

따라서 만들 수 있는 암호는 [BAAE, LAE, BKE, BAO, LO] 이다. DP[4]=5

---

* 5번째 자리 암호 숫자: 4 *

- 이전에 만든 암호에 현재 암호를 붙이는 경우(4='D')

[BAAE]+[D]= [BAAED]

[LAE]+[D]= [LAED]

[BKE]+[D]=[BKED]

[BAO]+[D]=[BAOD]

[LO]+[D]=[LOD]

 

-새로운 알파벳 문자로 암호를 만드는경우

4번째 숫자: 5 / 5번째숫자:4 => 54 => 그러나 26보다 크므로 만들 수 없다.

따라서 만들 수 있는 암호는 [BAAED, LAED, BKED, BAOD, LOD] 이다. DP[5]=5

 

여기서 규칙을 눈치챘는가?

현재 숫자가 0이아닌 1~9 인 수일때 두 케이스의 경우를 점화식으로 나타내면

- 현재 숫자를 알파벳으로 변환시켜서 이전에 만든 암호에 붙인 경우

DP[ i ]= DP[ i ] + DP [ i-1]

 

- (PW[i-1]*10+ PW[i])가 10~26 인 경우 알파벳으로 변환시켜서 생성하는 경우

DP[ i ] = DP[ i ] + DP[ i-2 ]

그리고 DP[0]=1을 설정해야 DP[2]=1이 성립된다.

 

(3) 중간에 0이 있는 경우

(예) 암호가 7220 일 때

- 1번째 숫자 7 (7='G')

만들 수 있는 암호 [G] => DP[1]=1

 

- 2번째숫자 2(2='B')

[G]+[B] => [GB]

만들 수 있는 암호 [GB]=> DP[2]=1

72는 26보다 크므로 생성할 수 없다. 

 

- 3번째 숫자 2(2='B')

[GB]+[B] = [GBB]

[G]+[22=>'V'] => [GV]

만들 수 있는 암호 [GBB, GV] => DP[3]=2

 

-4번째 숫자 0

0에 대한 대체 문자는 없으므로 3번째 숫자일때 만들 수 있는 암호에 그대로 붙여서 암호를 생성할 수 없다.

PW[3]*10 + PW[4] 가 10~26 사이의 숫자인지(알파벳으로 변환이 가능한 숫자인지)를 확인해야한다.

다행히도 20 나오므로 암호로 나타낼 수 있다.

[GB]+[20=>T] => [GBT]

만들 수 있는 암호는 [GBT]이므로 DP[4]=1이다.

---

[ 코드 (python) ]

import sys
input=sys.stdin.readline

MAX=5001
DP=[0]*MAX
PW=[0]*MAX
DIVIDER= 10**6

def solution(LEN):
    if PW[1]==0 or LEN==0:
        return 0
    
    DP[0]=1
    DP[1]=1
    for i in range(2, LEN+1):
        if 1<=PW[i]<=9:
            DP[i]=(DP[i]+DP[i-1])%DIVIDER
            
        tmp=(PW[i-1]*10)+PW[i]
        if 10<=tmp<=26:
            DP[i]=(DP[i]+DP[i-2])%DIVIDER
    return DP[LEN]
    
def main():
    password=input().strip()
    for i in range(1, len(password)+1):
        PW[i]=int(password[i-1])
    result=solution(len(password))
    print(result)
    
if __name__=='__main__':
    main()