[백준 2011] 암호코드 Python 풀이

[백준 2011] 암호코드 Python 풀이

📌 문제 분석

• 알파벳을 숫자로 암호화한 코드가 주어졌을 때, 가능한 해석의 경우의 수를 구하는 문제입니다
• A=1, B=2, ..., Z=26으로 암호화되어 있습니다
• 해석할 수 없는 경우는 0을 출력해야 합니다

🚨 시행착오

• 처음에는 단순 재귀로 접근했다가 시간 초과가 발생했습니다
• 중복되는 부분 문제가 많아 DP를 사용하기로 결정했습니다

처음 코드의 문제점

• 재귀 호출이 지수적으로 증가하여 시간 복잡도가 O(2^n)이 되었습니다
• 같은 인덱스에 대한 계산이 중복되어 비효율적이었습니다

어떻게 고쳤나요?

• DP 테이블을 활용하여 중복 계산을 제거했습니다
• bottom-up 방식으로 해결하여 시간 복잡도를 O(n)으로 개선했습니다

💡 해결 방안

s = input().strip()
n = len(s)

if s[0] == '0':  # 첫 문자가 '0'이면 해석 불가
    print(0)
    exit()

dp = [0] * (n + 1)
dp[0] = dp[1] = 1  # 빈 문자열과 첫 문자 해석 가능

for i in range(2, n + 1):
    one_digit = int(s[i - 1])      # 현재 한 자리 숫자
    two_digit = int(s[i - 2:i])    # 앞자리와 합친 두 자리 숫자

    if one_digit > 0:  # 단독 해석 가능
        dp[i] += dp[i - 1]

    if 10 <= two_digit <= 26:  # 두 자리 숫자로 해석 가능
        dp[i] += dp[i - 2]

print(dp[n] % 1000000)

🎯 이 문제의 핵심 포인트

1. DP를 활용한 효율적인 해결 방법
2. 한 자리, 두 자리 숫자를 모두 고려해야 함
3. 예외 처리 (0으로 시작하는 경우)
4. 모듈러 연산 적용

📝 예제로 이해하기

입력: 25114
출력: 6

해석 가능한 경우:
1) 2,5,1,1,4 -> BELLA
2) 25,1,1,4 -> YAA
3) 2,5,11,4 -> BEK
4) 25,11,4 -> YK
5) 2,5,1,14 -> BAN
6) 25,1,14 -> YAN

✨ 이번 문제를 통해 배운 점

1. DP 문제는 점화식을 세우는 것이 가장 중요합니다
2. 예외 케이스를 꼼꼼히 처리해야 합니다
3. 큰 수의 처리를 위한 모듈러 연산의 중요성을 배웠습니다

🔍 코드 설명

• dp[i]는 i번째 위치까지의 가능한 해석의 수를 저장합니다
• 각 위치에서 한 자리 숫자와 두 자리 숫자의 가능성을 모두 검사합니다
• 최종적으로 dp[n]을 1000000으로 나눈 나머지를 출력합니다

이 문제는 처음에는 어려워 보였지만, DP의 특성을 잘 활용하면 깔끔하게 해결할 수 있었습니다. 특히 점화식을 세우는 과정에서 많은 것을 배울 수 있었습니다.