[C언어] 백준 2011 : 암호코드

백준 2011 : 암호코드

 

문제 링크

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

2011번: 암호코드

 

 

문제 내용

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는 거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는 건 쉽게 알 수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화했다고 해봐. 그때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

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

 

 

Idea

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

 

문제가 제시한 암호문이 유효하기 위한 조건으로는 크게 2가지가 있다.

모든 인덱스마다, 아래와 같은 조건을 적어도 1개 충족하면 유효하다고 볼 수 있다.

1. 일의 자리 수가 1 ~ 9인 경우
2. 두 자릿수를 기준으로 11  ~ 26인 경우

위 조건을 토대로 만든 기본적인 점화식은 아래와 같다.

조건을 모두 충족하면 dp[i-1]과 dp[i-2]를 더하면 되지만 둘 중 하나만 충족한다면 해당 부분만 더해주면 된다.

💡 아래 코드에서는 우선 둘 다 더해준 다음 조건에 충족하지 않는 부분을 빼는 식으로 진행하였다.(line 30 ~ line 39)

 

반대로 제시한 암호문이 유효하지 않은 조건은 아래와 같다.

• '0'으로 시작하는 경우
• 0이 연속으로 들어오는 경우
• 일의 자리 수가 0이면서 십의 자리 수가 3 이상인 경우

 

이와 같은 조건들을 유의하여 코딩하면 끝!

자세한 내용은 코드에 주석으로 달아두었다.

 

 

Code

// [백준] 2011 : 암호코드
 
#include <stdio.h>
#include <string.h>
 
char cipher[5001];
int dp[5001];
 
int main() {
    // input
    scanf("%s", cipher);
    int size = strlen(cipher);
 
    // solution
    int result = 0;
    dp[0] = dp[1] = 1;
    if (cipher[0] - '0' != 0) {
        for (int i = 2; i <= size; i++) {
            // units & tens
            int one = cipher[i - 1] - '0';
            int ten = cipher[i - 2] - '0';
 
            // invalid cipher
            if (one == 0 && (ten == 0 || ten >= 3)) {
                result = 0;
                break ;
            }
 
            // dp
            int num = ten * 10 + one;
            dp[i] = dp[i - 1] + dp[i - 2];
 
            // 일의 자리 수가 0인 경우
            if (one == 0)
                dp[i] -= dp[i - 1];
            
            // 두 자리 수가 10이상 26이하가 아닌 경우
            if (num < 10 || 26 < num)
                dp[i] -= dp[i - 2];
            
            // update
            dp[i] = dp[i] % 1000000;
            result = dp[i];
        }
        // 암호문이 한 자리인 경우 예외처리
        if (size == 1)
            result = 1;
    }
 
    // output
    printf("%d\n", result);
    return (0);
}