[DP] 백준 2011번 - 암호코드

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

2011번: 암호코드

백준 DP문제다.

n번째 자리까지 가질 수 있는 경우의 수를 dp[n]에 저장하면

dp[string.length()]를 구해 출력하면 된다.

 

이 때 입력한 string의 i번째는 string[i-1]에 저장되어 있는데, 이 값을 갖고 

i) 1~9사이 값일 경우 dp[i]에 이전 자리까지 만들 수 있는 경우의 수를 더해준다. (dp[i] += dp[i-1];)

ii) 또한 string[i-2]*10 + string[i-1] 값이 10~26사이 값일 경우 역시 dp[i] += dp[i-2];를 해준다.

 

#include <iostream>
#include <string>
#define mod 1000000
 
using namespace std;
 
int dp[5001];
// dp[n] : n번째 까지 가질 수 있는 경우의 수
// 1자리인경우, 2자리인경우
int main(){
    string s;
    cin >> s;
    dp[0] = 1;
    for (int i = 1; i <= s.length(); i++){
        int x = s[i - 1] - '0';
        if (x >= 1 && x <= 9){
            dp[i] += dp[i - 1];
            dp[i] %= mod;
        }
        if (i == 1) continue;
        x = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
        if (10 <= x && x <= 26){
            dp[i] += dp[i - 2];
            dp[i] %= mod;
        }
    }
    cout << dp[s.length()] << '\n';
    return 0;
}