<2011> 암호코드 - DP

골드 V

 

 

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.
상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
상근: 얼마나 많은데?
선영: 구해보자!
어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

 

 

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.
암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

 

 

 

풀이

처음코드

import sys

n = " " + sys.stdin.readline().rstrip()
dp = [0] * (len(n))

if n[1] == "0" or (len(n) > 2 and int(n[1]) >= 3 and n[2] == "0"):
    print(0)

elif len(n) == 2:
    print(1)

else:
    dp[1] = 1
    dp[2] = dp[1]+1 if 0 < int(n[1:3]) <= 26 and n[2] != "0" else dp[1]

    for i in range(3, len(n)):
        if n[i] == "0":
            if int(n[i-1]) >= 3 or n[i-1] == "0":
                print(0)
                exit()
            else:
                dp[i] = dp[i-2] % 1000000
            continue
        if 10 <= int(n[i-1:i+1]) <= 26 and n[i] != "0":
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000
        else:
            dp[i] = dp[i-1] % 1000000

    print(dp[len(n)-1] % 1000000)

 

 

두번째 코드

import sys

n = " " + sys.stdin.readline().rstrip()
dp = [0] * (len(n))

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

else:
    dp[0] = 1
    dp[1] = 1

    for i in range(2, len(n)):
        one = int(n[i])
        tenth = int(n[i-1])*10 + int(n[i])
        if one > 0:
            dp[i] += dp[i-1] % 1000000
        if 10 <= tenth <= 26:
            dp[i] += dp[i-2] % 1000000

    print(dp[len(n)-1] % 1000000)

 

 

아 눈물 날뻔해...

처음에 나름 쉽게 풀려서 이게 왜 골드5 문제인가 했는데, 다.. 깊은 뜻이 있었음을..

 

일단 이 문제는, dp긴 한데, 그 알고리즘이 어렵다기보단 조악한 예외처리 때문에 정답률이 극악이 됐다.

(물론 내가 감자라서 그렇긴 함...)

 

 

 

TRY 1.

일단 기본적으로 점화식 찾는거는 그렇게 어렵진 않았음

dp[i] = dp[i-1] + dp[i-2]

 

예시 한번 써보니까 바로 보이기도 했고..

그래서 오 ㅋㅋ 나 천재 막이래 ㅋㅋ 이러면서 제출했는데, 틀렸다는거임

"0" 처리 때문에 그런가보다 대충 짐작은 했음.

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

이 문제 조건 보고 내가 떠올린 경우가

 

처음에 => 0으로 시작하면 에런가보다 => 틀림

2트 =>  그냥 0이 포함되면 에런가보다 => 틀림..???..??? 솔직히 그냥 알고리즘 잘못 짠 줄 알았는데, 질문게시판 보고 알았음....

 

이 문제에서의 잘못된 암호라는 것은

1. 0으로 시작 할 때 (0, 012, 07 .. 등등)

2. 0 앞에 0이 올 때 (00, 100, 4510021.. 등등)

3. 0 앞에 3 이상의 숫자가 올 때 (302, 105308.. 등등)

 

이 조건도 질문게시판 보고 알았음.. 

(솔직히 재능이 미친사람 빼고 저런 예외처리가 바로 눈에 보이는게.... 확통 재능러를 보는 고2로 돌아간 심정이었음ㅋ)

그래서 이때부터 대장정을...

 

 

 

TRY 2,3,4.............

 

여기서부터는 내가 딱히 할 말이 없는게,

98%까지 가놓고 런타임 에러, 그것도 인덱스 에러가 떠서 약간 멘붕이었음

인덱스 에러 10번을 마주한 심정.....

 

처음에는 인덱스 에러라길래, 당연히 for문 돌릴 때 양 끝 빠졌나 그 생각밖에 안함.

아니 거기에 너무 매몰돼서 다른 걸 못본듯...

근데 아무리 고쳐도 계속 인덱스 에러가 뜨길래 

뭔가 잘못됐음을 깨닫고 다른 사람 코드 찾아서 넣어봄.

 

..................... 정답 뜨고 나서야 보이더라

if n[1] == "0" or (int(n[1]) >= 3 and n[2] == "0"):

 

이 한줄 때문에 무수히 많은 런타임에러를................

n[2]가 존재할 거라는 보장이 없는데, 맨 윗줄에 예외처리 한답시고 저렇게 박아놓은게 문제였음...

 

내가 짠 코드를 의심하고 또 의심하고.... 사실 알고리즘부터 잘못됐던거 아닐까?... 하고...

그래서 맞았습니다 뜨고 나서 내 코드 고쳐서 다시 넣어봄. 

if n[1] == "0" or (len(n) > 2 and int(n[1]) >= 3 and n[2] == "0"):

 

n이 길이가 안되면 실행 안되게 조건 추가해줌. 바로 맞았다고 뜨더라.

 

예전에 알고리즘 스터디 할 때 멘토하는 친구가

이런 인덱스 쓰는 경우에서는 앞에 무조건 길이 체크하는 조건 박아놓는게 좋다고 했던게 생각이 남...

if 문 들어가지 않고, 바로 조건 읽는 순간 아니면 걸러지게 하는게 시간 면에서도 훨씬 빠르기도 하겠고..

 

+) exit() 처리하는거 별로 안좋아하는데 자꾸 쓰게됨...

조건만으로 처리하고 싶은데.... 으아아아아아아

 

------

 

아무튼 다 풀고나서, 내가 원래 쓴 코드랑 남 코드랑 좀 비교해봤는데

내가 참 멍청하게 코드를 짰다는 생각이...

 

내가 힘들었던 이유는 

0처리를 생각 안하고, 일반적인 경우의 알고리즘을 먼저 짬

=> 이후에 0처리를 하려는데 빼야되는 경우가 생각보다 너무 많음

==> 조건 넣는데 점점 지저분해짐

===> 그러다가 바보같은 실수함

(아닐지도 사실 이거 풀 때 너무 멘붕이어서 조건 막 쑤셔넣다가 그랬을지도...)

 

그런데 다른 분 코드 보니까, 

나처럼 0으로 시작하는거, 0 앞에 3이상 오는지, 0인지, 어쩌구 이런거 일일이 다 체크를 안하셨더라고..

for i in range(2, len(n)):
        one = int(n[i])
        tenth = int(n[i-1])*10 + int(n[i])
        if one > 0:
            dp[i] += dp[i-1] % 1000000
        if 10 <= tenth <= 26:
            dp[i] += dp[i-2] % 1000000

 

구글 어딘가에서 참고했는데, 기억이 안나요 ㅈㅅ합니다 주인분

 

다른분들이 푸신거에서 놀란 점

난 그냥 무지성 dp[i] = dp[i-1] + dp[i-2] 이거만 가지고 씨름 했는데

이걸 한자리수, 두자리수로 나눠서 조건을 걸어준게 신기했음...

(사실 아직도 완벽하게 이해 못한듯 ㅋㅋㅋ)

 

아무튼 다시 풀라고 하면 못풀거 같음...

max min 구하는거 마스터 했다고 생각 했는데 

경우의 수 나오니까 진짜 돌아버릴거 같음

확통의 악몽이 떠오를것만 같음..................

 

아..아아/....................

 

그리고 dp 하면 나오는 대표문제 >합분해< 나 이거 진짜 개어려워하는데 풀어야겠지...

이걸 마스터해야겠지..?... 아..........슬퍼