[종만북] 원주율 외우기(PI) (C++)

문제 출처 :

www.algospot.com/judge/problem/read/PI

algospot.com :: PI

문제 풀이 :

• 두 가지 함수를 작성하여 문제를 풀었다.
  첫번째는 주어진 문자열 S'에 대한 난이도를 반환하는 함수(calculate_score)
  두번째는 입력으로 주어진 문자열을 부분문제로 나누어 첫번째 함수에 넣고 최소값을 반환하는 함수 (solve)
• 첫번째 함수는 구현이기 때문에 시키는대로 구현하면 된다.
• 두번째 함수 같은 경우 봐야하는 점은 
  1) 어디서 시작할 것인가?
  2) 몇칸이나 할 것인가?
  라는 2가지 점을 이용하여서 작성하였다.
• 어떠한 길이의 문자열을 뜯어서 난이도를 측정하면 최초의 문자열에서 뜯어낸 문자열을 빼고 남은 문자열에 대해서 처음부터 다시하면 된다.
• 즉, 
  calculate_score(3글자)+ solve(4글자부터~)
  calculate_score(4글자)+ solve(5글자부터~)
  calculate_score(5글자)+ solve(6글자부터~)
  중 가장 작은 값을 구하면 문제는 해결 된다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int INF = 987654321;
string N;
int cache[10002];

int calculate_score(int idx_s,int idx_e)
{
    bool diff[4] = {1,1,1,1};
    string n = N.substr(idx_s,idx_e-idx_s+1);
    int i =0;

    //diff1
    for(i=0;i<n.size()-1;i++)
    {
        if(int(n[i])!=int(n[i+1]))
        {
            diff[0]=0;
            break;
        }
    }
    if(diff[0]) return 1;

    //diff2
    for(i=0;i<n.size()-1;i++)
    {
        if(int(n[i])+1 != int(n[i+1]))
        {
            diff[1]=0;
            break;
        }
    }

    if(diff[1]) return 2;
    diff[1]=1;
    for(i=0;i<n.size()-1;i++)
    {
        if(int(n[i])-1 != int(n[i+1]))
        {
            diff[1]=0;
            break;
        }
    }


    if(diff[1]) return 2;

    //diff4
    int num1 = int(n[0]);
    int num2 = int(n[1]);
    bool turn1 = 1;
    bool turn2 = 0;

    for(i =0;i<n.size();i++)
    {
        if(turn1)
        {
            turn1 = 0;
            turn2 =1;
            if(num1!=int(n[i]))
            {
                diff[2]=0;
                break;
            }
        }
        else if(turn2)
        {
            turn1=1;
            turn2=0;
            if(num2!=int(n[i]))
            {
                diff[2]=0;
                break;
            }
        }
    }
    if(diff[2]) return 4;

    int d = (int(n[1])-int(n[0]));

    for(i=0;i<n.size()-1;i++)
    {
        if(int(n[i+1])-int(n[i])!=d)
        {
            diff[3]=0;
            break;
        }
    }
    if(diff[3]) 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(calculate_score(begin,begin+L-1)+solve(begin+L),ret);
        }
    }
    return ret;
}

void init_()
{
    for(int i =0; i<10002;i++)
    {
        cache[i]=-1;
    }
}

int main()
{
    int c =0;
    cin >> c;

    for(int test_case=0; test_case<c;test_case++)
    {
        cin >> N;
        init_();
        cout << solve(0) <<endl;
    }

}