[백준/Python, Java] 2011 암호코드

📌문제 탐색하기

• A = 1, B = 2, ..., Z = 26으로하는 암호화 방식 사용
• 해당 방식을 사용할 경우 하나의 암호에 대해 암호의 해석이 여러 개 나올 수 있음
  • 25114 => "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN"
• 어떤 암호가 주어지면 해당 암호의 해석의 가짓수 구하기

입력

• 5000자리 이하의 암호(숫자로 이루어져있음)

출력

• 나올 수 있는 해석의 가짓수를 1000000으로 나눈 나머지 출력
• 암호를 해석할 수 없는 경우 0 출력

풀이 방법 생각해보기

복호화하기 위해 필요한 암호 글자수는 1~2자리이므로 dp[n]을 n자리까지 확인했을 때 가능한 해석의 가짓수로 상정하고, dp[n]에 대해 dp[n-2], dp[n-1]을 활용한 점화식을 세워서 풀이할 수 있다.

 

 

📌코드 설계하기

1. 변수 pwd에 암호를 입력받는다.
2. 만약 pwd의 첫글자가 '0'이라면 0을 출력하고 프로그램을 종료한다.
3. dp를 pwd 길이만큼의 요소를 가진 리스트로 초기화하고, dp[0]은 1로, 나머지 요소는 0으로 초기화한다.
4. dp[1]는 {pwd[0], pwd[1]}이 10~26 사이의 숫자인지 확인하고, {pwd[1]}이 1~9 사이의 숫자인지 확인해서 계산한다.
5. i를 2로 초기화하고, i가 n보다 작을 때 동안 아래 과정을 반복하며 dp[i]를 갱신한다.
   1. {pwd[i]}가 1~9 사이의 숫자라면 p1를 1로 초기화하고, 아니라면 0으로 초기화한다.
   2. {pwd[i-1], pwd[i]}가 10~26 사이의 숫자라면 p2를 1로 초기화하고, 아니라면 0으로 초기화한다.
   3. dp[i]를 (dp[n-1]*p1 + dp[n-2]*p2)를 1000000로 나눈 나머지로 갱신한다.
6. dp[len(pwd)-1]을 출력한다. 

 

📌시도회차 수정사항

python 1회차 (97% IndexError)

• pwd의 길이가 1일 때도 dp[1]을 초기화하려고 해서 IndexError가 났다. 해당 부분을 수정해주었다.

java 1회차 (63%(?) 틀렸습니다)

• 암호를 해석할 수 없는 경우(처음이 0으로 시작하는 경우) 0을 출력하지 않고 프로그램을 종료시켜버렸다.

 

📌정답 코드

Python

import sys
input = sys.stdin.readline

pwd = input().strip()
N = len(pwd)
if pwd[0] == '0':
    print(0)
    exit()
    
dp = [1] + [0]*(N-1)

for i in range(1, N):
    p1 = 1 if 1 <= int(pwd[i]) <= 9 else 0
    p2 = 1 if 10 <= int(pwd[i-1]+pwd[i]) <= 26 else 0
    
    if i == 1:
        dp[i] = p1 + p2
    else:
        dp[i] = (dp[i-1]*p1 + dp[i-2]*p2) % 1000000

print(dp[N-1])

 

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String pwd = br.readLine();
        
        if (pwd.charAt(0) == '0') {
            System.out.println(0);
            return;
        }
        
        int N = pwd.length();
        
        int[] dp = new int[N];
        dp[0] = 1;
        
        for (int i = 1; i < N; i++) {
            int num1 = Character.getNumericValue(pwd.charAt(i));
            int num2 = Integer.parseInt(""+pwd.charAt(i-1)+pwd.charAt(i));
            
            int p1 = (num1 >= 1 && num1 <= 9) ? 1 : 0;
            int p2 = (num2 >= 10 && num2 <= 26) ? 1 : 0;
            
            if (i == 1) {
                dp[i] = p1 + p2;
            } else {
                dp[i] = (dp[i-1]*p1 + dp[i-2]*p2) % 1000000;
            }
        }
        
        System.out.println(dp[N-1]);
    }
}