원주율 외우기

문제 : https://algospot.com/judge/problem/read/PI

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.

출력

각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.

코드 ( 종만북 참조 )

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring>

using namespace std;

string N;

const int INF = 987654321;

const int MAX = 10000;

int cache[MAX];

int compare(int a, int b)

{

string temp = N.substr(a, b - a + 1);

if (temp == string(temp.size(), temp[0])) return 1;

bool fourth = true;

for (int i = 0; i < temp.length() - 1; ++i)

if (temp[i+1] - temp[i] != temp[1] - temp[0])

fourth = false;

if (fourth && abs(temp[1] - temp[0]) == 1) return 2;

bool third = true;

for (int i = 0; i < temp.length(); ++i)

if (temp[i] != temp[i%2])

third = false;

if (third) return 4;

if (fourth) return 5;

return 10;

}

int solve(int begin)

{

if (begin == N.size())

return 0;

int& ret = cache[begin];

if (ret != -1)

return ret;

ret = INF;

for (int L = 3; L <= 5; ++L)

if (begin + L <= N.size())

ret = min(ret, solve(begin + L) + compare(begin, begin + L - 1));

return ret;

}

int main()

{

int C;

cin >> C;

while (C--)

{

cin >> N;

memset(cache, -1, sizeof(cache));

int result = solve(0);

cout << result << endl;

}

return 0;

}