[백준알고리즘] 2011번: 암호코드 -Python

[백준알고리즘] 2011번: 암호코드 -Python

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

2011번: 암호코드

글을 두 번째 쓰고 있다... 처음에 굉장히 장황해지고 두서가 없어서 다시 정리해서 쓰고, 내용에 맞게 풀이를 쓰려했는데 결국 같은 얘기가 됐다.

 

다른 분들이 잘 쓰신 코드를 보면 풀이 시간은 비슷하나 코드가 짧고 간단한 것들이 보여 밑에 같이 설명하도록 하겠다. 우선 내가 한 풀이부터 설명하겠다.

 

1. 곱셈을 이용한 경우의 수

내가 이용한 풀이이다. 우선은 문제의 내용부터 이해하면 다음과 같다. 암호를 단순히 알파벳과 숫자를 매칭 시킬 경우 발생할 수 있는 문제에 대해 설명하고 있다. 예를 들어 순서대로 숫자와 알파벳을 매칭 시킬 경우 A는 1이 되며 K는 11이 된다. 이때 11이란 수가 주어지면 AA로도, K로도 변환이 가능해진다. 마찬가지로 111이란 수가 주어지면 AAA, KA, AK로 변환이 가능해진다. 이렇게 두 자리 이상의 수가 있을 때 수가 이어지면서 해석이 가능해 암호 변환에 혼돈을 주는 경우를 임의로 "이어지는 수"라고 하겠다.

 

문제를 풀 때 "이어지는 수"를 확인하기 위해서 주어진 수를 하나씩 읽어 들이며 이전 수와 합쳐서 생각을 했다. 입력으로 11111가 주어졌다고 가정하면, 처음에는 맨 왼쪽의 1만 생각을 했다. 1은 A로 매칭이 가능하다.

다음은 하나의 인덱스가 더 추가되어 11이 되었다고 생각했다. 그러면 11은 위에서 말했듯이 AA와 K로 변환이 2가지로 될 수 있다.

다음은 하나의 인덱스가 더 추가되어 111이 되었을 경우, AAA와 KA, AK로 변환될 수 있다. 여기서 이렇게 변환될 수 있는 경우는 11 + 1이냐 1 + 11이냐로 나눠서 생각할 수 있다. 전자에 의해 AA + A와 K + A가 가능하고 후자에 의해 A + K가 가능하다. 따라서 (11의 경우의 수) + (1의 경우의 수)만큼이 존재할 수 있다.

마찬가지로 숫자를 늘려서 생각할 수 있다.

이러한 개념은 아래 다른 분들의 로직에서도 마찬가지로 나타나는 방법이다.

 

그리고 한 가지 더, 곱셈을 이용한 경우의 수가 적용된 곳은 주어진 예제 입력을 통해서 생각하게 되었다. 25114의 경우 25와 114로 "이어지는 수"를 나눠서 생각할 수 있다. 따라서 "이어지는 수" 25의 경우의 수는 2, 114의 경우의 수는 3이다. 이 두 경우를 곱해서 전체 경우의 수를 구하면 6이 되는 것으로부터 로직을 구현해나갔다. 아래 다른 분들의 짧은 코드는 이 경우를 생략했다고 볼 수 있다.

 

 

 

정리하자면 이 "이어지는 수"가 되기 위해서는 두 자리 수로 나눠서 봤을 때 10~26 범위의 수여야 가능하다. 그 외의 수는 모두 1자리당 1개의 문자로 매칭이 가능해진다.

 

단, 두 자리인 "이어지는 수"임에도 혼돈을 주지 않는 경우가 존재한다. 그 수는 10과 20이다. 이 경우에는 두 자리 수임에도 1개의 문자로 매칭이 가능해진다.

 

반대로 암호가 되지 못하는 조건도 존재한다. "이어지는 수"가 아닌데 0으로 시작하는 수가 그렇다. 예를 들어 00, 80 등이 그렇다. 즉 이 경우에는 하나의 인덱스씩 이동하며 확인을 할 때 현재의 인덱스가 0이며 이전의 인덱스가 1 또는 2 가 모두 아닌 경우가 그렇다는 것을 알 수 있다.

 

처음에 모든 경우를 다 잡아줬다고 생각했는데 아래의 반례들을 생각하지 못 했었다.

1203 ->1

101010 ->1

 

 

 

처음에 푼 코드에서 몇 자리 이어지냐에 따라서 cnt를 세는데 cnt[i] = cnt[i-1] + cnt[i-2]를 구하기 위해서 길이가 3인 리스트를 이용했다.

import sys

mod = 1000000
N = [0]
N += list(map(int, list(sys.stdin.readline().strip())))
cnt = [1, 1, 1]
res = 1

for idx in range(1, len(N)):
    if N[idx] == 0 and N[idx-1] != 1 and N[idx-1] != 2:
        res = 0
        break
    elif N[idx] == 0:
        res = (res * cnt[1])%mod
        cnt = [0, 1, 1]
        continue

    if (N[idx] < 7 and N[idx-1] != 1 and N[idx-1] != 2) or (N[idx] > 6 and N[idx-1] != 1):
        res = (res * cnt[2])%mod
        cnt = [1, 1, 1]
    else:
        cnt[0], cnt[1], cnt[2] = cnt[1], cnt[2], cnt[1] + cnt[2]
    
res = (res * cnt[2])%mod

sys.stdout.write(str(res))

 

아래는 정리를 위해 다시 풀었던 코드이다. 여기서는 같은 길이의 이어지는 수들은 같은 경우의 수를 갖는다는 것을 알고 딕셔너리를 이용해서 테이블을 만들었다. 리스트로 만들어도 되지만..! 그래서 cnt가 1로 초기화될 때마다 res에 table[cnt]를 곱해주도록 했다.

import sys

sys.setrecursionlimit(10**9)
number = '0'
number += sys.stdin.readline().strip()
length = len(number)
res, cnt, mod = 1, 1, 1000000
table = {0:1, 1:1, 2:2}

def get_count(cnt):
    if cnt in table.keys():
        return table[cnt]
    else:
        table[cnt] = (get_count(cnt-1) + get_count(cnt-2)) % mod
        return table[cnt]

for idx in range(1, length):
    now = int(number[idx-1:idx+1])

    if now == 10 or now == 20:
        cnt -= 1
    elif now > 10 and now <= 26:
        cnt += 1
    elif number[idx] == '0' and cnt == 1:
        res = 0
        break
    else:
        res = (res * get_count(cnt)) % mod
        cnt = 1

res = (res * get_count(cnt)) % mod
sys.stdout.write(str(res))

 

2. 간단한 동적 계획법

다른 분들의 짧은 코드를 보고 알게 된 풀이 방법이다. 물론 이 방법도 전반적인 아이디어는 동일하다. 하지만 위에서 "이어지는 수"를 나눠서 생각하고, 각각의 "이어지는 수"를 곱해 전체 경우의 수를 구한 방법과 다르게 간단하게 동적 계획법의 아이디어를 이용했다. 실행시간은 비슷하지만 이 코드가 괜찮아 보인다.

 

우선 이어지는 수에게 적용되는 dp[i] = dp[i-1] + dp[i-2] 라는 점화식을 이해했을 것이다. 이 아이디어를 그대로 이용하면 된다. 입력된 수를 하나씩 인덱싱하며 늘려갈 때 dp[i] = dp[i-1]을 해주는 것은 공통적인 부분이다. 이후 이전의 수와 합쳤을 때 10~26 사이의 수를 갖는 "이어지는 수"가 될 경우에는 dp[i] += dp[i-2] 를 추가로 더해준다. 여기서 10과 20의 처리도 한 번에 가능하며, 암호가 불가능한 경우의 처리도 dp[i] = d[i-1]에서 가능하다.

 

코드를 보면서 이해하는 것이 빠를 것 같다. 이렇게 코드를 짜면 10과 20의 경우에도 첫 번째 조건문이 아닌 두 번째 조건문에만 포함되기 때문에 적절한 처리가 가능하고, 100 같은 코드에서도 마지막 0은 두 조건문 모두 만족하지 못해 0을 출력하게 된다. 조건문 두 개와 처음 0으로 시작하는 것을 제외하는 코드로 모든 반례가 잡혔다.

import sys

N = sys.stdin.readline().strip()
if N[0] == '0': # 0으로 시작하는 경우
    sys.stdout.write("0")
    exit()

res = [1, 1] # 길이가 0일때 경우의 수 1, 길이가 1일때 경우의 수 1
mod = 1000000

for idx in range(1, len(N)):
    cnt = 0
    num = int(N[idx-1:idx+1])
    
    if int(N[idx]) > 0:
        cnt += res[-1]
    if num >= 10 and num <= 26:
        cnt += res[-2]
    res.append(cnt % mod)

sys.stdout.write(str(res[-1]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다