[Algospot] PI 원주율 외우기

문제 링크

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

핵심은

 

길이 3일때 난이도 + 나머지 수열 최적해

길이 4일때 난이도 + 나머지 수열 최적해

길이 5일때 난이도 + 나머지 수열 최적해

를 구하는 것인데 이때!

나머지 수열의 최적해를 구할때는 어떻게 나눴는지 중요하지 않다는 것입니다. 

어떤 자릿수 n부터 외우기 시작한다고 가정한다면

{n, n+1, n+2}

{n, n+1, n+2, n+3}

{n, n+1, n+2, n+3, n+4} 의 난이도를 구한 이후 최솟값을 사용하는 것입니다.

// //  main.cpp //  AlgorihmStudy // //  Created by sw on 2018. 9. 19.. //  Copyright © 2018년 sw. All rights reserved. // #include <cstdio> #include <string.h> #include <string> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <functional> const int INF = 987654321; using namespace std; string input; int dp[10002]; int getLevel(int head, int tail) {     string temp=input.substr(head,tail-head+1);     // 모든 숫자가 같은 경우     if(temp == string(temp.size(), temp[0]))         return 1;     // 숫자가 1씩 단조 증가 || 단조 감소     bool isProgress=true;     for(int i=0;i<temp.size()-1;i++)     {         if(temp[i+1]-temp[i] != temp[1]-temp[0])             isProgress=false;     }     if(isProgress && abs(temp[1]-temp[0])==1)         return 2;     // 두 개의 숫자가 번갈아나타남     bool isRotate=true;     for(int i=0;i<temp.size();i++)     {         if(temp[i] != temp[i%2])             isRotate=false;     }     if(isRotate)         return 4;     // 등차 수열     if(isProgress)         return 5;     // 이외의 모든 경우     return 10; } int solve(int start) {     // 기저사례     if(start == input.size())         return 0;     int& ret=dp[start];     if(ret != -1)         return ret;          ret=INF;          for(int i=3; i<=5; i++)     {         if(start+i <= input.size())             ret=min(ret,solve(start+i) + getLevel(start, start+i-1));     }     return ret; } int main(int argc, const char * argv[]) {     int tc;     scanf("%d",&tc);     //기저 사례     if(tc<0 || tc>51)         exit(-1);     while(tc--)     {         memset(dp,-1,sizeof(dp));         cin>>input;         cout<<solve(0)<<endl<<endl;     }     return 0; }