백준 2011번: 암호코드

백준 2011번: 암호코드

2011번: 암호코드

DP 문제는 언제풀어도 어려운 것 같다. DP는 풀이방법을 종이에다 손으로 직접 써봐야 알 수 있는 것 같다. 암호코드 문제는 생각해내는 것은 어렵지않은줄 알았는데 다른 사람들과의 풀이를 비교하니 접근방식 자체가 많이 달랐다. 그래서 내 코드에서 발생하는 예외사항이 다른 사람 코드에서는 발생하지 않았던 것이다. 결과적으로는 결국 혼자 해결하지 못하고 구글링으로 해결을 하였다.

 

문제 접근 방식은 다음과 같다.

25114라는 암호를 해독하기 위해서 숫자를 하나씩 접근하고

1의 자리 숫자인 경우와 2의 자리 숫자인 경우를 나누고

예외사항인 0인 경우만 조심하면 된다.

	2	5	1	1	4
1의 자리	2 dp[1] = dp[0] = 1	5 (dp[2] = dp[1]) = 1	1 (dp[3] = dp[2]) = 2	1 (dp[4] = dp[3]) = 2	4 (dp[5] = dp[4]) = 4
10의 자리(이전 자리 *10 + 현재 1의 자리)	X (0)	25 dp[2] = dp[2] + dp[0] = 1 + 1	51 (X)	11 dp[4] = dp[4] + dp[2] = 4	14 dp[5] = dp[5] + dp[3] = 6
DP (DP[0] = 1)	1	2	2	4	6

 

1의 자리 : DP[i] = DP[i - 1] (1~10)

10의 자리 : DP[i] = DP[i - 2] + DP[i] (10~26)

 

#include <iostream>
#include <string>
#define MAX 1000000
using namespace std;
long dp[MAX + 1];
int number[5001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string password;
    cin >> password;
    int len = password.length();
    dp[0] = 1;
    dp[1] = 0;
    for (int i = 1; i <= len; i++)
    {
        if (len == 1 && password[i] == '0')
        {
            cout << 0 << endl;
            return 0;
        }
        number[i] = password[i - 1] - '0';
    }

    for (int i = 1; i <= len; i++)
    {
        if (number[i] != 0)
        {
            if (number[i] < 10)
            {
                dp[i] = (dp[i - 1]) % MAX;
            }
        }
        //처음 숫자는 2자리 숫자를 고려하지 않는다.
        if (i == 1)
        {
            continue;
        }
        int two = number[i] + number[i - 1] * 10;
        if (two <= 26 && two >= 10)
        {
            dp[i] = (dp[i - 2] + dp[i]) % MAX;
        }
    }
    cout << dp[len];

    return 0;
}