책의 답안과 완전히 일치하지는 않지만,
포함해야할 조건들을 포함한 것 같은데
왜 오답이 나올까요..
~~~ c++
#include
#include
#include
#include
#include

std::string num;
int cache[10005];

//해당 조각(begin ~ end) 의 난이도 계산
int classify(int begin, int end)
{
//해당 조각 가져오기
std::string P = num.substr(begin, end - begin + 1);
int first = P[0];
int sec = P[1];
int diff = sec - first;
bool check = false;

//난이도 1인지 확인
if (diff == 0)
{
    for (int i = 1; i < (end - begin); i++)
    {
        if (P[i] == P[i + 1])
            check = true;
        if (!check)
            break;
    }
    if (check)
        return 1;
    check = false;
}

//난이도 2인지 확인 (단순증가)
else if (diff == 1)
{
    for (int i = 1; i < (end - begin); i++)
    {
        if (P[i+1] - P[i] == 1)
            check = true;
        if (!check)
            break;
    }
    if (check)
        return 2;
    check = false;
}

//난이도 2인지 확인 (단순감소)
else if (diff == -1)
{
    for (int i = 1; i < (end - begin); i++)
    {
        if (P[i+1] - P[i] == -1)
            check = true;
        if (!check)
            break;
    }
    if (check)
        return 2;
    check == false;
}

//난이도 4인지 확인
for (int i = 1; i < (end - begin + 1); i++)
{
    if (i % 2 == 0)
        check = P[i] == first;
    else
        check = P[i] == sec;
    if (!check)
        break;
}
if (check)
    return 4;
check = false;

//난이도 5인지 확인
for (int i = 1; i < (end - begin); i++)
{
    if (P[i+1] - P[i] == diff)
        check = true;
    if (!check)
        break;
}
if (check)
    return 5;

//다 아니면 난이도 10
return 10;

}

//시작 index가 begin 일 때 최소난이도 반환
int memorize(int begin)
{
int& ret = cache[begin];
//cache에 저장된 값 있으면 바로 반환
if (ret != -1)
return ret;
int avail = num.size() - begin;
if (avail < 3)
return 0;

//잔여 num의 갯수에 따라 가능한 경우를 나누고, 그 중 최소값을 return
if (avail == 3)
{
    return ret = classify(begin, begin + 3) + memorize(begin + 3);
}
if (avail == 4)
{
    int a = classify(begin, begin + 3) + memorize(begin + 3);
    int b = classify(begin, begin + 4) + memorize(begin + 4);
    return ret = std::min(a, b);
}
else
{
    int a = classify(begin, begin + 3) + memorize(begin + 3);
    int b = classify(begin, begin + 4) + memorize(begin + 4);
    int c = classify(begin, begin + 5) + memorize(begin + 5);
    int tmp = std::min(a, b);
    return ret = std::min(tmp, c);
}

}

int main(void)
{
int C;
scanf("%d", &C);
for (int tc = 0; tc < C; tc++)
{
//초기화
num.erase(0, num.length());
memset(cache, -1, sizeof(cache));

    std:: cin >> num;
    printf("%d\n", memorize(0));
}
return 0;

}
~~~