2011번: 암호코드

문제 링크

https://www.acmicpc.net/problem/2011

2011번: 암호코드

 

문제 풀이 코드

#include <iostream>
#define DIV 1000000

using namespace std;
const int MN = 5001;
long long dp[MN];
int input[MN];

bool isApha(int a){
    if(0<a&&a<=26) return true;
    else return false;
}

int main(void){
    ios::sync_with_stdio(false); cin.tie(NULL);
    
    string inputS; cin>>inputS;
    
    //스트링을 int형 배열로 변경
    for(int i=1; i<=inputS.length(); i++) input[i]=inputS[i-1]-'0';
    
    //문자열이 0으로 시작할 경우 : 0을 출력하고 실행 종료
    if(input[0]=='0'){
        cout<<'0'; return 0;
    }

    dp[0]=1; //초기값 

    for(int i=1; i<=inputS.length(); i++){
        
        if(isApha(input[i])) dp[i] = (dp[i-1] + dp[i])%DIV;

        if(i==1) continue; //첫번째 수이면 continue; (전에 숫자까지 확인할 필요 없으니)

        int tmp = input[i]+input[i-1]*10;
        
        if(tmp>=10&&isApha(tmp)){
            dp[i]=(dp[i-2]+dp[i])%DIV;
        }
        
    }
    
    cout<<dp[inputS.length()];
    
    return 0;
    
}

DP는 너무너무 어렵다 ㅠ