[백준(BOJ)] 2011번: 암호 코드(C++)

입/출력

- 입력: 5000자리 이하의 숫자 암호
- 출력: 나올 수 있는 해석의 가짓수 % 1000000, 암호를 해석할 수 없는 경우에는 0을 출력

제출 코드

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string code;
    
    cin >> code;
    
    int len=code.size();
    vector<int> DP(len+1);
    DP[0]=DP[1]=1;
    
    if(code[0]=='0') {
        cout << 0 << endl;
        return 0;
    }
    
    for(int i=2; i<=len; i++){
        int one=code[i-1]-'0';
        int two=(code[i-2]-'0')*10+one;
        
        if(one>=1 && one<=9) DP[i]=(DP[i-1]+DP[i])%1000000;
        //if(i==1)continue; // for first digit, not consider 2digit
        if(two>=10 && two<=26) DP[i]=(DP[i-2]+DP[i])%1000000;//add one case

    }
    cout << DP[len] << endl;
    
    return 0;
}

• DP[a] = b : a번째까지 읽을 수 있는 단어 개수는 b개이다.

• 1234의 겨ㅇ우, DP[1] = 1, DP[2] = (각각 1자리로 본 경우 DP[1]+ DP[2]) + (두자리로 본 경우 DP[0]+DP[2] ) = 1 + 1 = 2
• DP[0]=1
• 한자리씩 보는 경우 n-1까지 읽을 수 있는 단어 수 + DP[n] ⇒ DP[n] = DP[n-1] + DP[n] ⇒ Arr[n]이 1~9인 경우
• 두자리 보는 경우 n-2까지 단어 수 + DP[n] ⇒ DP[n] = DP[n-2] + DP[n] ⇒ n이 첫번째가 아닌 Arr[n-1]*10+Arr[n]이 10 ~ 26인경우?
• 이때 string0번째 인덱스부터 문자시작인데 DP는 1에 매칭됨. 1번짜 자리 경우의 수는 항상1이므로 DP[0]=DP[1]=1로 두고, 2부터 계산하면 one은 code[i-1]-‘0’, two=(code[i-2]-‘0’)*10+one으로 문제없이 계산이 됨 DP는 원래 인덱스 i를 사용하면됨
• 최종적으로 DP[len] 구하면 모든 경우의 수가 계산됨

제출 결과