백준 2011 파이썬

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

2011번: 암호코드

2011번은 Dynamic Programming 문제입니다.

DP 문제는 한 번 생각이 안 나면 아무리 식을 길게 쓰면서 노가다를 해보고 규칙을 찾으려고 해도 잘못 찾게 되거나, 아예 못 찾게 되는 경우가 많은 것 같습니다(물론 저 한정). DP 문제를 더 풀어보고, 예전에 풀었던 것들도 다시 풀어보면 데이터가 쌓이면서 좀 더 빠르게 규칙을 찾고 식을 찾을 수 있을 것 같지만, 아직은 그런 경지에는 다다르지 못한 것 같습니다.

 

2011번은 아예 식을 잘못 생각해서 출발했더니 예외 처리를 너무 많이 하게 되었고, 코드가 잘못되었다는 걸 깨닫고 혼자서 씨름하다가 구글링 + 백준 질문들을 통해서 해결했습니다. 또한 질문 게시판을 보다 보면 아시겠지만 2년 전에 데이터가 빠지거나 추가되어 예전 블로그 포스팅을 보면 '??이게 포함된다고..?'싶은 예제들이나 예외들이 있습니다! 최근 블로그들을 참고하는 게 정답일 것 같습니다.

 

2011번은 점화식을 찾는 과정이 조금 생소했습니다. 밑에 손그림과 설명을 남겨두겠지만, 이해가 되지 않으신다면 차라리 가장 하단에 코드를 먼저 보고 다시 손그림과 설명을 읽는 방식이 조금 더 수월할 수 있습니다.

 

우선 2011번 예시에는 25114를 입력했더니 6이 나옵니다.

 

일단 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

 

이렇게 여섯가지가 있습니다. 

 

여섯가지를 직접 찾아보면 우선 i번째 인덱스일때 i-1번째 인덱스를 10의 자리수로 둘 수 있느냐 없느냐에 따라 경우의 수가 발생한다는 것까지는 이해할 수 있을 것 같습니다.

더 풀어서 설명하자면, 앞서 2번째 인덱스(5)에서 1번째 인덱스(2)를 참고했을때, 10의 자리수를 2라고 두고 5와 합치면 25가 됩니다. 25는 암호화 하는 범위(1~26)에 포함되기 때문에 2,5로 표현할 수도 있지만, 통으로 25로 표현할 수도 있습니다. 즉 경우의 수가 2개 생기게 됩니다.

그러나 3번재 인덱스인 1에서는 얘기가 달라집니다. 2번째 인덱스 값이 5이므로 만약 5가 십의 자리수로 오게 된다면 51이 되는데, 이는 범위에 어긋나는 값입니다. 즉, 오직 5/1로 표현하게 되어 경우의 수가 1개가 됩니다.

 

여기서 dp 식을 어떻게 세워야 할 지 고민을 올바르게 하느냐 빙빙 둘러 가느냐의 차이가 생길 것 같습니다.

 

이제는 손으로 그린 그림을 첨부하며 설명을 진행하겠습니다.

결과부터

필기하는 모습을 GIF로 만들었는데, 중간중간에 화면 녹화가 좀 잘려서 결과 이미지부터 첨부합니다. 이걸로 바로 이해가 된다고 하시면 그냥 바로 문제를 풀면 될 것 같습니다.

 

가장 처음 dp의 초기값들은 0이라고 합시다. dp = [0,0,0,0,0] 이때 인덱스 시작이 0이 아니라 1이라고 가정합니다. 

 

1. 2일때 2만 되므로 경우의 수는 1개 입니다. dp[1] = 1

 

2. 5일때는 입력 값이 25라고 생각한다면 2,5 그리고 25 이렇게 경우의 수가 각각 1개 씩 나옵니다. 최종 합은 dp[2] = 2

 

3. 여기서부터 조금 헷갈릴 수 있는데, 그럴때는 직접 손으로 써서 경우의 수를 세보면 됩니다. 251일때는 51이 나올 수 없기 때문에 앞서 dp[2] = 2에서 변화가 발생할 수 없습니다. 2/5/1 그리고 25/1 이렇게 두 가지 경우밖에 없기 때문입니다.

즉, dp[3] += dp[2] -> dp[3] = 2

 

4. 그리고 2511일때는 1/1, 11이 나올 수 있기 때문에 경우의 수가 2가지 발생합니다. 

 

펜 굵기나 색을 바꾸기 위해 창을 열었다 닫았다 해서 gif 가독성이 조금 떨어지네요 ㅠㅠ 

여기서 이제 1일때 11일때, 각각 dp[3]의 값과 dp[2]의 값을 화살표로 끌어다가 합했는데, 그 이유에 대해 더 자세히 설명해보겠습니다.

 

1일때는 앞에 2,5,1을 이용한 수의 조합에 1을 덧붙인 것과 같습니다. dp[3] = 2였는데, 2/5/1/1 이거나 25/1/1 일 수 밖에 없기에 dp 값이 변할 수가 없다는 뜻입니다. 즉, dp[4] += dp[3]일 수 밖에 없습니다. 

 

11일때는 동일한 원리이지만, 2,5,1,1에서 1,1를 뺀, 즉 dp[2]의 값을 더해줘야 합니다. 2/5/11이거나 25/11이기 때문입니다. 즉, dp[4] += dp[2]가 됩니다. 

 

5. 마지막, 4일때, 25114일때도 마찬가지 입니다. dp[5] += dp[3], dp[5] += dp[4] 

 

그렇다면 이제 점화식을 만들고 결론을 만들 수 있을 것 같습니다.

즉, 1의 자리 수만 가능하다면 dp[i] += dp[i-1],

그 전 인덱스 값을 10의 자리수로 포함해서 그게 범위(10~26)에 들어간다면 dp[i] += dp[i-2]

 

그런데 또 앞서 본 두 번째 인덱스, 5일때가 그럼 논리에 맞지 않습니다. dp[2] += dp[1], dp[2] += dp[0]이 되어야 하는데 우리는 현재 dp[0]이 없죠. 즉, dp의 길이가 입력값의 길이보다 1개 더 길어야 하고, dp[0]의 값에는 1이 디폴트로 들어가있어야 논리가 맞습니다. 

 

그리고 저는 거기에 맞춰서 입력값 code에도 처음에 code[0] = 0이라는 의미없는 값을 넣어주어 인덱스를 맞춰주었습니다.

 

그렇다면 dp 계산 로직 식을 이렇게 정의할 수 있습니다.

length = len(code) #입력받은 암호 숫자가 code
dp = [0] * length
dp[0] = dp[1] = 1 #dp[0] = 1 디폴트값, dp[1]은 예시 25114에서 2에만 해당하므로 무조건 1이 됨.

for i in range(2, length):
    first = int(code[i]) #한자리 수
    tenth = int(code[i-1])*10 + int(code[i])#그 전 인덱스를 참고해서 두 자리수로 구성
    if first > 0: dp[i] += dp[i-1] #한 자리 수가 0보다 클때
    if tenth >= 10 and tenth <= 26: dp[i] += dp[i-2] #두 자리 수가 10이상 26이하일때

 

이제 로직을 다 짰으면 예외 처리를 해줘야 합니다.

문제에서는 '암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.' 라고 되어있습니다. 암호가 잘못된다는 건 어떤 경우인지 단순히 생각해보면, 우선 0이 있겠습니다. 범위는 1~26인데 0을 입력 받으면 해석할 수 없겠죠. 00020, 001, 01 등 맨 처음에 0이 붙으면 다 잘못된 경우라고 볼 수 있습니다. 

 

그렇다면 0이 중간에 들어가 있으면 어떻게 될까요? 예시로 1304를 생각해보겠습니다. 중간에 10, 20이 아닌 30이 들어가 있다고 생각할 수도 있고, 불필요한 0이 들어간 04가 들어갔다고 생각해도 좋겠습니다. 이것 또한 정해진 규칙에 어긋나는 암호이기 때문에 0이 출력되어야 합니다. 그렇다면 맨 처음에 입력 받자마자 for문을 돌면서 이런 예외를 따로 걸러내야 할까요? 그럴필요가 없습니다.

 

저희가 짠 로직에 따르면, 우선 dp[1] = 1, dp[2] = 2까지는 쉽게 생각할 수 있습니다.

그 다음 index가 3이 되었고, code[3] = 0입니다. 한자리수 일때는 0이고, 두 자리 수 일때는 30이죠. 저희의 조건문에는 아무것도 걸리지 않기 때문에 dp[3]에는 그 어떠한 값도 더해지지 않습니다.

즉, dp[3] = 0이라는 값이 그대로 유지됩니다. 그리고 index가 4가 되면 dp[3] = 0이기 때문에 dp[4] = 0이 되어 결과 값은 암호를 해석할 수 없는 경우인 0이 출력됩니다. 

 

즉, 맨 처음에 0이 붙는 경우만 입력 받은 후 바로 처리 해주면, 다른 예외들은 로직 내에서 알아서 0을 출력할 수 있게 됩니다.

 

 

<전체코드>

import sys
code = [0] #인덱스 값 맞추기용 0 초기값
code += list(sys.stdin.readline())
code.pop() #'\n'날리기

if code[1] == '0': 
    print(0)
    exit(0)

length = len(code)
dp = [0] * length
dp[0] = dp[1] = 1

for i in range(2, length):
    first = int(code[i])
    tenth = int(code[i-1])*10 + int(code[i])
    if first > 0: dp[i] += dp[i-1]
    if tenth >= 10 and tenth <= 26: dp[i] += dp[i-2]

print(dp[length-1]%1000000)

 

블로그를 여러 군데 봤는데 이해하기가 쉽지 않아서 최선을 다해서 풀이를 해보려고 했습니다. 이해가 되었을지는 모르겠습니다ㅠ.ㅠ 혹시 제가 잘못 기재한 부분이 있다면 언제든지 댓글 남겨주세요 감사합니다