BOJ 2011 암호코드(Alphacode)

 

문제 링크 : https://www.acmicpc.net/problem/2011

2011번: 암호코드

 

입력을 문자열 str 로 받아서 처리한다.

p 를 문자열에서 현재 처리할 index 라 하자.

dp[p] 는 p 를 시작 위치로 하는 부분 문제의 결과값을 의미한다.

세 가지 가능성이 있다.

 

1. 더 이상 진행이 불가능한 경우 -> str[p] 가 '0' 

이 경우 해당 수를 알파벳에 대응시킬 방법이 없다.

더 이상 진행하지 않고 return 0 을 하면 된다.

가짓수를 세는 문제니 0 을 돌려준다는 것은 불가능하다는 의미.

 

2. 해당 수 하나를 알파벳에 대응시키는 경우 -> str[p] 가 '0' 가 아니면 언제나 가능

1~9 까지에 해당되는 A~I 로 변환하면 된다.

 

3. 해당 위치와 그 다음의 수를 합쳐서 하나의 알파벳에 대응시키는 경우

이 경우 str[p] 는 1 이거나 2 여야 하고, 

str[p] 가 2 인 경우는 str[p+1] 이 6 이하여야 한다.

deal 함수가 처리한다.

 

#include<bits/stdc++.h>

using namespace std;

const int mmod=1e6;
string str;
int sz, dp[5000];

bool deal(int p){
    if(p+1>=sz) return false;
    if(str[p]-'0'>2) return false;
    if(str[p]=='2' && str[p+1]-'0'>6) return false;
    return true;
}

int recur(int p){
    if(p==sz) return 1;
    if(str[p]=='0') return 0;
    
    int &ret=dp[p];
    if(ret!=-1) return ret;
    
    ret=0;
    ret+=recur(p+1);  // 하나의 수를 하나의 알파벳에 대응
    if(deal(p))
        ret+=recur(p+2);  // 두 개의 수를 하나의 알파벳에 대응 (가능한 경우에) 
    
    ret%=mmod;
    return ret;
}

int main(){
    memset(dp,-1,sizeof dp);
    cin >> str;
    sz=str.length();
    
    printf("%d\n",recur(0));
}