[백준] 2011번 암호코드 - C++

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자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

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

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

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

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

---

경우를 나누어서 생각을 하였다.

dp[i][j] 배열을 생성하여 i는 현재 판단하고 있는 글자의 위치, j는 이전 숫자와 합쳐서 판단하였는지 여부이다.

고려해야 할 상황으로는

1. '0' 이 들어온 경우

- 앞의 숫자가 1 혹은 2가 아니면 오류이다.

- 앞의 숫자와 무조건 합쳐야 하므로

- dp[i][0] = 0 // 무조건 결합

- dp[i][1] = dp[i - 1][0] // 이전 숫자가 결합하지 않은 경우에만 결합

2. 이전 숫자가 1인 경우.

- 현재 숫자가 무엇이든 앞의 숫자와 결합할 수도 있다. 다만, 이전 숫자가 그 전 숫자와 결합하지 않은 상태에만 결합할 수 있으므로

- dp[i][0] = dp[i-1][0] + dp[i-1][1]; // 이전 숫자와 결합하지 않기 때문에 이전 모든 경우를 더함 

- dp[i][1] = dp[i-1][0] //이전 숫자가 결합하지 않은 경우에만 결합

3. 이전 숫자가 2 + 현재 숫자가 0 ~ 6인 경우.

- 위와 같다.

4. 이외의 경우 

- 결합이 안되므로 단순히 숫자 하나로 판단하기 때문에.

- dp[i][0] = dp[i - 1][0] + dp[i - 1][1]; // 이전 숫자와 결합하지 않기 때문에 이전 모든 경우를 더함 

- dp[i][1] = 0; // 결합 불가능

#include <iostream>

using namespace std;
int dp[5001][2];
bool err = false;
int main(){
    string s;
    cin >> s;
    if(s[0] == '0')
        err = true;
    dp[0][0] = 1;
    dp[0][1] = 0;
    for(int i = 1 ; i < s.length();i++){
        char cur = s[i];
        char prev = s[i - 1];
        if(cur == '0'){
            if (prev == '1' || prev == '2'){
                dp[i][0] = 0;
                dp[i][1] = dp[i - 1][0];
            }
            else{
                err = true;
                break;
            }
        }
        else{
            if(prev == '1'){
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
                dp[i][1] = dp[i - 1][0];
            }
            else if (prev == '2' && (cur >= '0' && cur <= '6')){
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
                dp[i][1] = dp[i - 1][0];
            }
            else{
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
                dp[i][1] = 0; 
            }
        }
        dp[i][0] %= 1000000;
        dp[i][1] %= 1000000;
    }
    int ans = dp[s.length()-1][0] + dp[s.length()-1][1];
    ans %= 1000000;
    if(err)
        cout << 0;
    else
        cout << ans;
}

---

    구상한 생각을 글로 적고 풀 수 있을 것 같아 풀었지만 막상 코드를 적어보니 구현을 할 수가 없었다. 이때는 1차원 dp 배열을 활용하였지만 이내 이전과 결합을 하였는지 여부에 대해 생각을 해보아야겠다고 생각했다. 그래서 2차원 배열로 dp 배열 두줄을 활용하여 문제를 풀었다. 문제를 구상하고 풀이하고 에러를 고치고 하는 것이 생각대로 착착 진행되어 기분이 좋았다. 문제도 구상을 한 뒤 코드를 작성하니 깔끔하고 빠르게 풀 수 있었던 것 같다.

    오랜만에 코드를 짜는 것 같다. 요 며칠 약속도 있고 캡스톤 디자인 프로젝트도 하고 이러면서 개인 공부를 많이 하지 못했다. 또, 42 서울 본과정에 합격하여서 OT도 하고 새로운 과제도 시작하였다. 그래서 학교 수업 복습이나 코딩 문제 풀이 등을 좀 못 푼 것 같은데 이제 다시 열심히 해야겠다!!