2011 : 암호코드 - Python

접근

---

예전에 도전했다가 실패했었던 문제.

1	2	3	4	5
B	BE, Y	BEA, YA	BEAA, YAA, BEK, YK	BEAAD, YAAD, BEKD, YKD, BEAN, YAN

만약 1≤ code[i - 1] * 10 + code[i] ≤ 26라면, dp[i] = dp[i - 2] + d[i - 1]

아니라면 dp[i] = dp[i - 1]

풀이

---

다른 분들 풀이를 참고하니 좀 더 간단한 방법도 있었다. 특정 조건을 만족할 때만, 값을 더해주는 방식이다.

 

만약 현재 자리가 0이 아니라면 일단 문자로 만들 수 있다. 따라서, 바로 직전에 만든 문자열에 문자 하나를 추가하면 된다.

이를 식으로 나타내면 아래와 같다.

for idx in range(1, len(code)):
    if code[idx] > 0:
            dp[idx] += dp[idx - 1]

또한, 두 글자를 합쳤을 때 10과 26의 사이에 있다면 문자를 만들 수 있다. 따라서, 두 글자 전에 만든 문자열에 문자를 하나 추가하면 된다.

for idx in range(1, len(code)):
    if 10 <= code[idx - 1] * 10 + code[idx] <= 26:
            dp[idx] += dp[idx - 2]

위에서 나올 수 있는 경우의 수는 총 4가지이다.

1. 현재 자리수가 0이 아니고, 직전 자리수와 합쳐서 문자를 만들 수 있는 경우
   • 이 때, dp[idx] = dp[idx - 2] + dp[idx - 1] 이 된다.
2. 현재 자리수가 0이고, 직전 자리수와 합치면 문자를 만들 수 있는 경우
   • 이 때, dp[idx] = dp[idx - 2]가 된다.
3. 현재 자리수가 0이 아니지만 직전 자리수와 합쳐도 문자를 만들 수 없는 경우
   • 이 때는, dp[idx] = dp[idx - 1] 이 된다.
4. 현재 자리수가 0이고, 직전 자리수와 합쳐도 문자를 만들 수 없는 경우
   • 이 경우 dp[idx]는 0에서 갱신되지 않는다.

따라서, 1000과 같이 해독할 수 없는 코드에는 아래와 같은 dp테이블이 생성된다.

0	1	2	3	4
1	1	1	0	0

전체 코드

---

1차 풀이

import sys

# print = sys.stdout.write
input = sys.stdin.readline

# 반드시 아래 두 라인 주석 처리 후 제출
f = open("input.txt", "rt")
input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출
MOD = 1_000_000
code = "0" + input().rstrip()
dp = [0] * (len(code) + 1)
# 점화식 처리하기 위한 장치
dp[0] = 1

def main():
    # 순서상 문자열의 두 번째
    # dp의 첫 번째
    # dp[1] = 1

    for idx in range(1, len(code)):
        prev, current = int(code[idx - 1]), int(code[idx])
        if current == 0:
            # 두 부분을 합쳐도 문자 성립이 안되면
            if prev * 10 + current > 26 or prev * 10 + current == 0:
                print(0)
                return
            # 두 부분을 합치면 문자 생성은 가능
            dp[idx] = dp[idx - 2] % MOD
            continue

        # 현재 숫자만 문자로 변환 가능
        if prev * 10 + current > 26 or prev * 10 + current < 10:
            dp[idx] = dp[idx - 1] % MOD
            continue

        # 모두 가능
        dp[idx] = (dp[idx - 2] + dp[idx - 1]) % MOD

    print(dp[len(code)] % MOD)

if __name__ == "__main__":
    main()

 

풀이 참조 후 개선

import sys

# print = sys.stdout.write
input = sys.stdin.readline

# 반드시 아래 두 라인 주석 처리 후 제출
f = open("input.txt", "rt")
input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출
MOD = 1_000_000
code = [0] + list(map(int, input().rstrip()))
dp = [0] * (len(code) + 1)
# 점화식 처리하기 위한 장치
dp[0] = 1

def main():
    if code[1] == 0:
        print(0)
        return

    for idx in range(1, len(code)):
        # 길이를 늘려줬으므로 첫 번째 자리부터 시작가능
        if code[idx] > 0:
            dp[idx] += dp[idx - 1]

        temp = code[idx - 1] * 10 + code[idx]
        if 10 <= temp <= 26:
            dp[idx] += dp[idx - 2]
        dp[idx] %= MOD

    # 강제로 한 글자 늘렸으니 -1 해줘야함
    print(dp[len(code) - 1] % MOD)

if __name__ == "__main__":
    main()