[백준] 2011번 : 암호코드 (파이썬)

DP / DFS + Memorization 문제

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

 

접근 방식

• 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 경우의 수 구하기 
  -> 같은 암호에 대해 반복해서 해석하는 것을 방지하고 계산 효율성을 높이기 위해 dp나 memorization 기법을 활용하자 !
  -> 암호의 i번째 자리에 대해 이미 구한 가짓수는 dp 또는 memo 배열에 저장해 두자.
• dfs만 사용하는 것은 불필요한 연산을 반복하게 되므로 memorizatino 기법을 활용하여 memo 배열에 기록하자.
  -> 만약, memo에 기록해둔 값이 있다면 dfs를 재귀호출하지 않고, memo에 기록해둔 값을 바로 리턴하자.

 

💡 풀이코드 (성공)

'''
1. 처음에 생각했던 dp 배열 : r = len(str), c = 26(알파벳 갯수)
   변경 후 : r = len(str), c = 2 (1: 알파벳이 한자리 수일 경우 / 2: 알파벳이 두자리 수일 경우)
2. 암호가 잘못되어 해석할 수 없는 경우 -> 0 처리 
3. 14% 반례
    01 -> 정답 : 0 / 출력 : 1
'''

import sys 
sys.setrecursionlimit(10 ** 9)

str = sys.stdin.readline()
memo = [[-1] * 2 for _ in range(len(str))]

def dfs(idx, str, ii):
    if idx == len(str) - 1:
        return 1 

    if memo[idx][ii] != -1: return memo[idx][ii]

    way = 0
    for i in range(1, 3):
        nIdx = idx + i
        if nIdx < len(str) and 0 < int(str[idx:nIdx]) <= 26 and str[idx:nIdx][0] != "0": # 2. 0처리 추가 (0 < )
            # 3. "01" -> 맨 앞에 "0"이 오는 경우 예외 처리 추가
            way += dfs(nIdx, str, i - 1)
        memo[idx][ii] = way % 1000000
    return memo[idx][ii] % 1000000

print(dfs(0, str, 0) % 1000000)
# print(int("01")) -> 1

 

👩🏻‍💻 위의 코드

1. r = len(str), c = 2(알파벳을 해석할 자릿수)인 memo 배열 생성 
(1: 알파벳이 한자리 수일 경우 / 2: 알파벳이 두자리 수일 경우)

 

- memo 2차원 배열을 몇 x 몇 형식으로 만들고, 어떠한 값을 저장하면 좋을지 고민했다.

- 처음에는 r = len(str), c = 26(알파벳 갯수)인 2차원 배열을 생각했지만, 이러한 경우 불필요한 column 수가 추가될 뿐더러 이 배열을 어떻게 활용할지조차 감이 잡히지 않았다.

- 이에 어떻게 memo 배열을 만들어야 이 값을 적절하게 활용할 수 있을지 고민하던 찰라에 문제의 핵심을 다시 짚어보기로 했다.

- 예를 들어, 암호 = 25114에서 숫자 하나 -> 알파벳 하나로 해석되는 경우와 숫자 두개 -> 알파벳 하나로 해석되는 경우가 있기 때문에 "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN"인 총 6가지의 경우의 수가 나올 수 있다. 맨 앞의 2가 B로 해석될 수도, 25로 볼 경우에는 Y로 해석될 수도 있는 것이다.

- 따라서, c의 값을 알파벳을 해석할 자릿수를 나타내는 2로 설정하기로 하였다. 알파벳을 int로 변경할 경우 1 ~ 26 사이의 값이 나온다. 이 말은 즉, 1 ~ 26 사이의 int값은 하나의 알파벳으로 해석 가능하므로 한자릿 수의 int값을 알파벳 하나로 해석할지, 아니면 두자릿 수의 int값을 알파벳 하나로 해석할지를 memo 배열에 기록해주면 되는 것이다.

 

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

 

1) 변경 전 : 암호에 "0"이 나올 경우에도 dfs를 호출하였음.

 if nIdx < len(str) and int(str[idx:nIdx]) <= 26: # 2. 0처리 추가 (0 < )
 	way += dfs(nIdx, str, i - 1)

 

2) 변경 후 : 알파벳 -> int로 변환한 수의 범위를  1 ~ 26으로 설정해줌으로써 암호에 "0"이 나올 경우에는 dfs 호출 X

 if nIdx < len(str) and 0 < int(str[idx:nIdx]) <= 26: # 2. 0처리 추가 (0 < )
 	way += dfs(nIdx, str, i - 1)

 

 

3. "0"이 맨 앞에 나오는 경우 예외 처리

 

- 예를 들어, 암호가 "011"인 경우를 생각해보자.

정답 : 0

출력(기존 코드): 1

이 경우에는 int 한자리를 알파벳 하나로 해석하든, int 두자리를 알파벳 하나로 해석하든 무조건 전체 경우의 수가 0이다. 맨 앞의 알파벳 "0"을 대체할 알파벳이 없기 때문이다. 이 말은 즉, 맨 앞에 "0"이 온다면 암호가 잘못되어 암호를 해석할 수 없는 경우란 뜻이다.

 

변경 후 : 암호의 맨 앞에 "0"이 나올 경우에는 정상적인 암호가 아닌 이상한 암호이다. 따라서, 어떠한 경우의 수도 없으므로 dfs를 호출하지 않게 변경해주었다. -> 암호의 맨 앞에 "0"이 나올 경우에는 경우의 수가 무조건 0이다.

 if nIdx < len(str) and 0 < int(str[idx:nIdx]) <= 26 and str[idx:nIdx][0] != "0": # 2. 0처리 추가 (0 < )
 	way += dfs(nIdx, str, i - 1)