암호코드 (BOJ 2011)

문제

문제 설명

• 암호를 만들 때 A=1, B=2, C=3...., Z=26으로 지정하여서 나타낸다.
• 예를 들어서 ABCZ는 12326(1/2/3/26)으로 나타낼 수 있다.
• 하지만 12326은 ABCZ로 해석할 수도 있지만 1/23/2/6으로 나누어서 AWBF로 도 해석할 수 있다.
• 이 문제에서는 위와 같은 경우의 개수를 출력하면 된다.

문제 해설

• 만약 암호의 맨 처음 부분이 0으로 주어진다면 암호를 해독할 수 없기 때문에 0만 출력해 주고 종료한다.
• 이후부터 dp탐색을 시작해 준다.

1. dp [i]: (i번째 자리까지의 암호해독의 경우의 수) 
2. i번 위치에서 (i-1) 번의 한자리 숫자가 1 이상이고 9 이하이면 dp [i]+=dp [i-1] 연산을 해준다.
3. i번 위치에서 (i-2)~(i-1) 번의 두 자리 숫자가 10 이상이고 26 이하이면 dp [i]+=d [i-2] 연산을 해준다.

• 예를 들어서 3번째 자리에 있을 때를 경우 생각해 보자.

• 앞의 1~2번째의 두 자리 숫자는 10 이상이고 26 이하이기 때문에 dp [3]+=dp [1]을 해준다.
• 하지만 2번째 자리 숫자는 0이기 때문에 업데이트를 해주지 않고 넘어간다.

최종 코드

#include<iostream>
using namespace std;
const int mod=1000000;
int dp[5001];
string s;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>s;
    int n=s.size();
    if(s[0]=='0'){
        cout<<0<<'\n';
        return 0;
    }
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        int l=s[i-1]-'0';
        int r=(s[i-2]-'0')*10+l;
        if(l>=1&&l<=9)dp[i]=(dp[i]+dp[i-1])%mod;
        if(r>=10&&r<=26)dp[i]=(dp[i]+dp[i-2])%mod;
    }
    cout<<dp[n];
}

• s [0]==0이면 이 부분은 해석할 수 없기 때문에 0을 출력해 주고 코드를 종료한다.

 if(s[0]=='0'){
        cout<<0<<'\n';
        return 0;
    }

• 다음으로는 dp [0]=dp [1]=1로 초기화시켜준다.
• 이후에는 한자리 숫자와 두 자리 숫자로 암호 해독이 가능한지 확인해 주면서 dp탐색을 해준다.

dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        int l=s[i-1]-'0';
        int r=(s[i-2]-'0')*10+l;
        if(l>=1&&l<=9)dp[i]=(dp[i]+dp[i-1])%mod;
        if(r>=10&&r<=26)dp[i]=(dp[i]+dp[i-2])%mod;
    }

이미지 클릭