[BOJ] 2011 : 암호코드

문제 링크

2011번: 암호코드 (acmicpc.net)

2011번: 암호코드

암호가 주어졌을 때 가능한 해석의 수를 구하는 문제.

 

풀이

알파벳 A~Z를 1~26으로 암호화 하기로 했다. 띄어쓰기가 있다면 1 1 과 11을 구분할 수 있겠지만 암호에 띄어쓰기가 없기 때문에 암호가 11이라고 하면 "AA"와 "K"로 2가지로 해석 가능하다.

여기서 주의해야 할 점은 0은 아무런 암호도 아니기 때문에 해석이 불가능하다. 그렇기 때문에 10이 들어오면 1 0 으로 구분해서는 해석할 수 없고 10으로 해석해야한다.

그렇기 때문에 입력으로 0 하나만 주어진다면 해석이 불가능한 코드이므로 0 을 출력하고 종료하면 된다.

아무래도 각 자리의 숫자를 하나하나 봐야하기 때문에 int 형보다는 string 형으로 입력받는 것이 편하다.

나는 DP배열을 DP[시작점][끝점] 으로 설정해서 시작점부터 끝점 인덱스에 해당하는 암호가 해석될 수 있는 경우의 수를저장해 두었다.

25114

예제1을 예시로 들자면 0~1 인덱스를 보면 "25"이다 이는 2, 5로도 해석될 수 있고 25로도 해석될 수 있기 때문에

DP[0][1]에는 2의 값을 저장해 두었다. 사실 출발점은 항상 0이기 때문에 DP를 굳이 2차원 배열로 만들지 않아도 됐지만 중간에 아이디어를 바꾸게 돼서 코드를 많이 고치지 않으려 하다보니까 이렇게 됐다.

DP[문자열의 길이] 로 1차원 배열로 만드는게 메모리 면에서는 더 효율적이기 때문에 좋은 코드이다.

0~2번 인덱스까지 즉 "251"을 모든 경우의 수로 나누어 보자.

2 5 1, 25 1, 2 51 이렇게 3가지가 있다.

빨간색으로 칠한 2 5와 25는 0~1까지 봤을 때 나올 수 있는 경우이다.

초록색으로 칠한 2는 0~0 까지 봤을 때 나올 수 있는 경우이다.

DP[0][2] 는 DP[0][1] * DP[2][2] + DP[0][0] * DP[1][2] 로 볼 수 있는데 DP[1][2] 는 DP[1][2] 의 값을 그대로 갖고오면 안된다. 그렇다면?

임의의 좌표 i 에 대해 DP[0][i] = DP[0][i-1] * DP[i][i] + DP[0][i-2] * (i-1 ~ i 두 자리가 자체만으로 암호가 될 수 있는지?) 로 볼 수 있다.

여기서 봐야할 점은 뒤의 식인 DP[0][i-2] * (i-1 ~ i 두 자리가 자체만으로 암호가 될 수 있는지?) 이 부분이다.

2 51 이렇게 분리해서 보는 경우에는 뒤에 51을 5 1로 나누지 않고 51 그 자체로 암호로 해석될 수 있는지만 고려하면 된다. 무슨 말이냐 하면 2 51 에서는 2 5 1 로 나뉘는 경우는 2 5 1 에서 이미 고려됐기 때문에 생각하지 않아도 된다.

그렇다면 51은 51 > 26 이기 때문에 51 자체만으로는 암호가 될 수 없다. 그렇기 때문에 뒤의 식은 0이 된다.

따라서 DP[0][2] = DP[0][1] * DP[2][2] = 2 * 1 = 2

DP[0][3]("2511") = DP[0][2] * DP[3][3] + DP[0][1] * (2 ~ 3 까지가 자체만으로 암호가 될 수 있는지?)인데

DP[0][2] = 앞에서 구한대로  2이고 DP[3][3] = 1이다.

DP[0][1] = 2 이고 뒤의 두자리인 "11" 은 <= 26 이기때문에 자체만으로 암호가 될 수 있다.

따라서 DP[0][3] = 2 * 1 + 2  = 4 이다.

그런데 DP[i][i] 라고 해서 다 값이 1인 것은 아니다. i 번째 인덱스 값이 '0' 이라면 DP[i][i] = 0 이된다.

이렇게 해서 DP[0][N-1] 의 값을 출력해주면 정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 5000 + 5;
int N;
int DP[MAX_N][MAX_N];
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    cin >> S;
    if (S.size() == 1 && S[0] == '0') {
        cout << "0\n";
        return 0;
    }
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '0') {
            continue;
        }
        DP[i][i] = 1;
    }
    for (int i = 0; i < S.size() - 1; i++) {
        string temp = S.substr(i,2);
        if (S[i] == '0') {
            DP[i][i + 1] = 0;
            continue;
        }
        else if (S[i + 1] == '0') {
            if (stoi(temp) <= 26) {
                DP[i][i + 1] = 1;
            }
            continue;
        }
        if(stoi(temp) <= 26)
            DP[i][i + 1] = 2;
        else DP[i][i + 1] = 1;
    }
    for (int i = 2; i < S.size(); i++) {
        DP[0][i] = DP[0][i - 1] * DP[i][i];
        if (DP[i - 1][i] == 1 && stoi(S.substr(i-1,2))<= 26) {
            DP[0][i] += DP[0][i - 2];
        }
        else if(DP[i-1][i] == 2)DP[0][i] += DP[0][i - 2] * (DP[i-1][i] - 1);
        DP[0][i] %= 1000000;
    }
    cout << DP[0][S.size() - 1]<< "\n";
    return 0;
}