백준 2011. 암호코드

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

2011번: 암호코드

이 문제 못풀어서 아래 블로그의 설명을 그대로 옮겨왔다. 

참고 블로그: https://pupuduck.tistory.com/7

[백준 2011][DP][C++] 암호코드

1. 문제 접근

251104로 고려해보자. 

(1) 2를 볼 때, 경우의 수는 (2)

(2) 5를 볼 때, 경우의 수는 (2, 5), (25)

(3) 1을 볼 때, 경우의 수는 (2, 5, 1), (25, 1)

(4) 1을 볼 때, 경우의 수는 (2, 5, 1, 1), (25, 1, 1), (2, 5, 11), (25, 11)

(5) 0을 볼 때, 경우의 수는 (2, 5, 1, 10), (25, 1, 10)

(6) 4을 볼 때, 경우의 수는 (2, 5, 1, 10, 4), (25, 1, 10, 4)

 

정리해보면,

1. (2)에서 (3)으로 갈 때는 (2)에서 나온 경우에 1을 붙이는 방법밖에 없다. 51은 알파벳이 아니기 때문

2. (3)에서 (4)로 갈 때는 (3)에서 나온 경우에 1을 붙이는 방법과 (2)에서 나온 경우의 수의 (3)과 (4)를 붙이는 방법이 있다. 

3. (4)에서 (5)로 갈 때는 (3)에서 나온 경우에 (4)와 (5)를 붙이는 방법박에 없다. 0은 알파벳이 아니기 때문

 

수식으로 나타내면

1. 만약 보고 있는 수가 0이 아니고, 앞에서 본 수와 붙였을 때 10보다 작으면 dp[i] = dp[i-1]

2. 만약 보고 있는 수가 0이 아니고, 앞에서 본 수와 붙였을 때 10이상이면 dp[i] = dp[i-1] + dp[i-2]

3. 만약 보고 있는 수가 0이면 dp[i] = dp[i-2]

 

2. 코드

#include <iostream>
using namespace std;
#define mod 1000000;
string str;
int dp[5002]; // i번째 자리까지 봤을 때 해석할 수 있는 단어 개수 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> str;
    if(str[0] == '0')
    {
        cout << '0';
        return 0;
    }
    dp[0] = 1; dp[1] = 1;
    for(int i = 2; i <= str.size(); i++)
    {
        if(str[i-1]>'0')
        {
            dp[i] = dp[i-1]%mod; 
        }

        int n = (str[i-2]-'0')* 10 + str[i-1] -'0';
        if(10 <= n && 26 >= n)
        {
            dp[i] = (dp[i]+dp[i-2])%mod;
        }
    }
    cout << dp[str.size()];
}