[C++] 백준 2011번 - 암호코드

---

0. 문제

 

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

 

1. 아이디어

 

일단 이 문제에서는 고려해줘야할 점들이 생각보다 많았다.

우선 문제에서 dp는 숫자의 개수별로 만들 수 있는 경우의 수라고 정했다!

 

그리고 만약 N-1번째 숫자와 N번째 숫자가 암호의 범위(1~26) 사이에 있다면 dp[N] = dp[N-1] + dp[N-2] 이고 범위 밖이라면 dp[N] = dp[N-1] 이라는 걸 알아냈다.

(왜냐면 저번 문제에서 사용한 아이디어처럼, dp[N-1]에서 그냥 N번째 숫자 하나만 독립적으로 뒤에 붙여주는 경우 그리고 dp[N-2]에다가 N-1번째와 N번째 숫자가 이루는 두자리수 암호를 붙여주는 경우로 나눌 수 있기 때문이다.)

 

하지만 해석할 수 없는 암호의 경우엔 0을 출력하라고 했다.

해석할 수 없는 암호란, 범위의 숫자로써 판단할 수 없는 숫자가 끼여있다는 건데.

예를 들어, 200132 에서 0과 같은 경우 또는 7230 의 경우를 말한다.

 

또 예를 들어, 7220 에서 3번째 2는 2번째 2와 범위의 수를 이룰 수 있지만 그렇게 되면 뒤에 있는 0이 혼자 남게 되어 범위의 숫자로써 판단할 수가 없게 된다!

 

2. 소스코드

 

#include <iostream>
#define DIV 1000000
long long dp[5000];
int main()
{
    std::string code;
    std::cin >> code; // string으로 암호 입력 받음
 
    if (code[0] - '0' == 0)
    {
        std::cout << "0";
        return 0;
    }
    dp[0] = 1; // 첫번째 숫자에 대한 검사 및 dp[0] 초기화!
 
    if (code[1] - '0' == 0)
    {
        if (code[0] - '0' > 2)
        {
            std::cout << "0";
            return 0;
        }
        else dp[1] = 1;
    }
    else
    {
        int temp = (code[0] - '0') * 10 + code[1] - '0';
        if (temp > 10 && temp <= 26) dp[1] = 2;
        else dp[1] = 1;
    } // 두번째 숫자에 대한 검사 및 dp[1] 초기화!
 
    for (int i = 2; i < code.length(); i++)
    {
        int pre = code[i - 1] - '0';
        int post = code[i] - '0';
        if (post == 0)
        {
            if (pre == 0 || pre > 2)
            {
                std::cout << "0";
                return 0;
            }
            else // 1이나 2인 경우
            {
                dp[i] = dp[i - 2];
                continue;
            }
        }
 
        if (pre * 10 + post > 10 && pre * 10 + post <= 26)
        {
            dp[i] = (dp[i - 1] + dp[i - 2]) % DIV;
            continue;
        }
        dp[i] = dp[i - 1];
    }
 
    std::cout << dp[code.length() - 1];
}

 

3. 결과

 

 

4. 피드백

 

• 경우의 수 고려 잘하자.. 아이디어는 빨리 캐치했는데 자꾸 놓치는게 생기네.

• 스트링 입력받고 하는 걸 헷갈렸다.. 다시 한번 보자!

---

TO DO LIST: string

 

---