백준 알고리즘 - 암호코드 (2011) [Python]

 

 

 문제

 

www.acmicpc.net/problem/2011

2011번: 암호코드

 

 

 

 

 

 

 문제 상황

 

- 숫자가 주어지고 대응되는 암호코드를 만들 때, 가능한 암호 코드의 수를 출력한다. 숫자가 커질 경우를 대비해 1,000,000으로 나눈 수를 출력한다. 암호로 변경이 불가능한 경우 0을 출력한다.

 

 

 

 

 

 

 

 해결 전략

 

- 우선 암호로 변경 불가능한 경우는 크게 두가지이다. 숫자가 아닌 값이 입력되거나, 0이 들어가는데 10, 20처럼 처리 가능한 숫자가 아닌 00, 40 처럼 알파벳에 대응될 수 없는 경우가 존재하는 상황이다.

 

- 암호는 숫자로 이루어져있다는 조건이 있지만 연습을 위해 알파벳 등 숫자가 아닌 문자열이 들어가는 경우를 고려하였다.

 

 

 

 

 

 

 

 코드

 

# dp를 활용
from sys import stdin,setrecursionlimit
input = stdin.readline
code = input().strip()
if code[0] == "0" or not code[0].isdecimal(): 
    print("0")
    exit()
mod = 1000000
cache = [1, 1] # 0번 인덱스와 1번 인덱스 연산을 위해 1 ,1 로 초기화해준다. 
for i in range(1, len(code)):
    cnt = 0
    if int(code[i]) > 0 and code[i].isdecimal():
        cnt += cache[-1] # 지금 관찰하는 i인덱스의 바로 앞 값 i-1 인덱스까지 만들 수 있는 개수를 더해준다.
    if 10<= int(code[i-1:i+1])<27:
        cnt += cache[-2] # i-2번째까지의 암호 개수에 i-1,i 인덱스의 숫자를 2자리 숫자로 넣는 개념
    cache.append(cnt%mod)
print(cache[-1])
 
 
# dfs를 활용
setrecursionlimit(100000)
code = input().strip()
cnt = 0
def search(i):
    global cnt 
    if i >= len(code)-1: # code의 끝까지 갔다면
        cnt = (cnt + 1)%1000000 # 개수를 한개 늘려준다.
        return None
    if code[i] == "0" or not code[i].isdecimal() : return None # 0이 숫자가 될 수 없으므로
    if code[i:i+2].isdecimal() and 10 <= int(code[i:i+2]) <= 26: # 다음 자리수를 포함해서 2자리수가 가능하면
        search(i+2) # 2자리 수를 경우에 포함하고 그 이후를 체크해본다.
    search(i+1) # 한자리 수를 알파벳에 포함하고 그 다음을 체크한다.   
search(0)
print(cnt)
 

 

 

 

 

 

 

 

 

 

 해설

 

- 최초의 아이디어는 dfs였다. pruning을 반복하며 조건을 최소화했지만 속도 이슈가 발생하였다. 

 

- 알파벳은 최대 26까지로 1자리에서 2자리로 결정난다. 여기서 피보나치의 아이디어를 차용할 수 있다. 조건을 양분하여 2자리 수가 가능한 경우는 숫자 2개를 제외한 경우를 포함하고, 아니라면 하나의 숫자로 연산하는 과정을 처리하였다. 

 

- 주의해야할 포인트는 크게 두가지인데, 00의 경우 당연히 cache가 0 , 0이 발생하므로 더이상 피보나치는 의미가 없다. 0이 나오되 40처럼 26을 넘는 경우가 발생하면 무조건 cache가 0이 된다. 그럼 0 다음 숫자가 2같이 0이아닌 숫자가 나오더라도 그 이전 index의 값이 0이므로 0, 02는 10보다 작으므로 cnt를 더해주지 않으므로 무조건 0이 나온다. 즉, 어떤 경우에도 cache에 0이 한번나오면 그 이후 cache 값들은 전부 0일수 밖에 없다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 한개, 혹은 두개 요소가 결정자가 될 때에는 항상 피보나치, dp를 고려하자

 

- dfs도 풀이 자체가 틀린 것은 아니지만 아무리 pruning해도 속도 이슈가 있다면 완전히 다른 알고리즘을 생각해볼 필요가 있다.