[ALGOSPOT] PI

algospot.com/judge/problem/read/PI

algospot.com :: PI

<문제>

(주의: 이 문제는 TopCoder 의 번역 문제입니다.)

가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

1. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
2. 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
3. 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
4. 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
5. 그 외의 경우 난이도: 10

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

<입력>

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

<출력>

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

 

<아이디어>

현재까지의 난이도의 합을 저장하는 DP 배열을 만들어, 최솟값을 저장한다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int check(int k, int size, vector<int>& v)
{
    bool flag = false;
    for(int i=k;i<k+size;i++)
    {
        if(v[i]==v[i+1]) flag = true;
        else
        {
            flag = false;
            break;
        }
    }
    if(flag) return 1;
    for(int i=k;i<=k+size;i++)
    {
        if(k%2==i%2 && v[k]==v[i]) flag = true;
        else if((k+1)%2==i%2 && v[k+1]==v[i]) flag = true;
        else
        {
            flag = false;
            break;
        }
    }
    if(flag) return 4;
    int sub = v[k]-v[k+1];
    for(int i=k;i<k+size;i++)
    {
        if(v[i]-v[i+1]==sub) flag = true;
        else
        {
            flag = false;
            break;
        }
    }
    if(flag && abs(sub)==1) return 2;
    else if(flag) return 5;
    return 10;
}
 
int PI(int k, vector<int>& v, vector<int>& dp)
{
    if(k==v.size()) return 0;
    int& ret = dp[k];
    if(ret != 100000) return ret;
    for(int i=2;i<5;i++)
    {
        if(k+i<v.size())
            ret = min(ret, PI(k+i+1, v, dp)+check(k, i, v));
        else return ret;
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        string s;
        cin>>s;
        vector<int> v(s.size());
        for(int i=0;i<s.size();i++)
            v[i] = s[i]-'0';
        vector<int> dp(s.size(), 100000);
        cout<<PI(0, v, dp)<<endl;
    }
 
    return 0;
}