백준 2011번 : 암호코드

  알고리즘 자체가 어려운 문제는 아니었는데 깔끔하게 예외처리를 하는데 시간을 더 많이 쏟았다. 하나하나 다 막아주다가 사고방식을 바꿔서 그래도 나름 깔끔하게 예외 처리해서 만족.

---

  풀이

  코드를 여러 방법으로 해석하기 위해서는 붙어 있는 두 숫자가 1에서 26 사이여야 한다. 그 외의 경우는 반드시 한 가지로만 해석 할 수 있거나 해석할 수 없는 잘못된 코드이다. 먼저 dp를 정의해보자.

 

dp [i] : 0번째부터 i-1번째까지만 코드가 있을 때 해석 가능한 경우의 수

 

  따라서 i-2번째와 i-1번째 수를 두 자릿수로 봤을 때 10 이상 26 이하면 i-1번째 수를 단독으로 해석할 수도 있고 두자리수로 해석할 수 있다.

 

10 이상 26 이하 : dp [i] = dp [i-1] + dp [i-2]

26 이상 : dp [i] = dp [i-1]

 

  예제의 코드를 이용해 예를 들어보자면 25114라는 코드에서 제일 뒤에 있는 4라는 숫자를 단독으로 해석할 수도 있고 앞에 있는 1과 함께 14로 해석할 수도 있다. 그러므로 dp [5] = dp[4]+dp[3]이다. 만약 코드가 25134였다면 4라는 숫자는 단독으로밖에 해석할 수 없다. 이 경우는 dp[5] = dp [4]이다.

 

  예외 처리

  예외는 코드에 0이 포함될 때 발생한다. 0이 정상적인 코드로 작동하기 위해서는 앞의 숫자와 합쳐서 10 또는 20이 될 때뿐이다. 그 외의 경우는 모두 비정상적인 코드로서 동작한다. 상황에 따른 결과를 아래 표로 표현했다. code [i-1]는 i-1번째 숫자이고 target은 i-1번째와 i-2번째를 두 자리 숫자로 봤을 때의 값이다.

 

	code[i-1] == '0'	code[i-1] > '0'
target이 10이상 26이하	단독 해석 불가능, 결합 해석 가능	단독 해석 가능, 결합 해석 가능
	dp[i] = dp[i-2]	dp[i] = dp[i-1] + dp[i-2]
그 외의 경우	잘못된 코드	단독 해석 가능, 결합 해석 불가능
	dp[i] = 0	dp[i] = dp[i-1]

 

  위를 표를 코드로 옮기면 아래와 같다.

 

#include <iostream>

using namespace std;

string code;
int dp[5004];
int DIV = 1000000;

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> code;
    
    int len = code.size();
    
    dp[0] = 1;
    if(code[0] == '0') dp[1] = 0;
    else dp[1] = 1;
    
    for(int i = 2; i <= len; i++)
    {
        if(code[i-1] > '0') dp[i] = dp[i-1];
        int target = (code[i-2] - '0') * 10 + (code[i-1] - '0');
        if(10 <= target && target <= 26) dp[i] = (dp[i] + dp[i-2]) % DIV;
    }
    
    cout << dp[len];
    
    return 0;
}