[Python] 백준 2011 - 암호코드

1. 문제 - 백준 2011 암호코드

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

 

이 문제는 DP (다이나믹 프로그래밍, 동적 계획법) 로 풀 수 있다.

첫번째 예시인 25114를 고려해보면 2, 25, 251, 2511, 25114.. 로 진행하면서 각각 암호화할 수 있는 문자가 이전 문자를 사용해서 만들 수 있다는 점에서 짐작할 수 있다.

 

✅ 풀이 과정

1) 첫번째 예시인 25114의 정답이 6으로 나오는 과정을 살펴보면,

 

2/5/1/1/4

25/1/1/4

25/11/4

25/1/14

2/5/11/4

2/5/1/14

 

여기서 반복문을 통해 차례대로 수를 방문했을 때,

현재 인덱스에서 10부터 26까지의 수로 만들 수 있는지 없는지에 따라서 경우의 수가 추가됨을 알 수 있다.

이를 유의하며 경우의 수에 따라 DP값이 어떻게 바뀌는지 확인하며 규칙을 찾아야한다.

 

2) 

https://archive-me-0329.tistory.com/23?category=965963

백준 2011 파이썬

 

이분의 그림이 가장 이해가 잘 되어서 그림을 토대로 이해해보고자 했다.

n = "0" + input()  # 2)

if n[1] == "0":      # 3)
  print(0)
  exit()

_len = len(n)
dp = [0] * 5001  # 5000자리 이하의 암호   # 1)
dp[0] = dp[1] = 1

for i in range(2, _len):             # 1)
  first = int(n[i]) #한자리 수
  tenth = int(n[i-1])*10 + int(n[i])
  if first > 0: dp[i] += dp[i-1]
  if tenth >= 10 and tenth <= 26: dp[i] += dp[i-2]

print(dp[_len-1] % 1000000)

 

1) 먼저, 5000자 이하의 암호가 주어지므로 인덱스가 0에서 시작하는것을 고려해 5001 size의 DP 배열을 초기화한다.

그리고나서 해당 인덱스 수가 1부터 9사이라면 (first > 0) dp[i-1]값을 더하고, 이전의 수를 합쳐 10부터 26사이의 수를 만들 수 있다면 dp[i-2] 값을 더한다.

 

ex) 2511 일 경우

- 2: 1 (첫번째 자리수는 항상 1이므로 dp[1] = 1로 초기화)

- 25: 25, 2/5 2가지 가능   (dp[i-1] 값과 dp[i-2] 값을 더함 --> 여기서 dp[0]값이 1이어야 값이 성립하므로, dp[0] = 1로 초기화)

- 251: 2/5/1, 25/1 2가지 가능  (51은 불가하므로 dp[i-1] 값을 더함)

- 2511: 2/5/11, 2/5/1/1, 25/11, 25/1/1 4가지 가능 (dp[i-1] + dp[i-2])

 

2) 여기서 입력받은 암호 앞에 "0"을 더하는 이유는, #1) 에서 반복문을 돌때 인덱스 2가 암호 두번째 글자를 가리키게 하게 하기 위함이다.

3) 이부분은 예외처리하기 위함인데, 이 조건을 쓰지 않으면 35% 쯤에서 틀린다.

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

 

라는 조건이 있으므로, 해당 암호가 0으로 시작하면 해석할 수 없는 경우이므로 이때 0을 출력하고 종료시킨다.