(알고스팟) 원주율 외우기

                                                      예              난이도
모든 숫자가 같을 때                           333, 5555          1
숫자가 1씩 단조 증가하거나 감소할때       23456,3210     2
두 개의 숫자가 번갈아가며 나타날 때         323, 54545    4
숫자가 등차수열을 이룰 때                       14,8642        5
이 외의 모든 경우                                17912, 331       10


원주율의 일부가 주어질 때, 난이도의 합을 최소화하도록 숫자들을 세 자리에서 다섯자리까지 끊어 읽는다. 최소 난이도를 계산하라

예제)
5(입력케이스)
12341234
11111222
12122222
22222222
12673939

출력:
4
2
5
2
14

public class PI {

private static int N;
private static int cache[];
private static final int INF=999;
private static String input="";

public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
           
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(reader.readLine());
cache=new int[N];
Arrays.fill(cache, -1);
input=reader.readLine();
System.out.println(memorize(0));
}
private static int memorize(int start)
{
if(start==N)return 0;
if(cache[start]!=-1)return cache[start];

int ret=INF;

for(int next=start+3;next<=start+5;next++){
if(next<=input.length())
ret=Math.min(ret, memorize(next)+classify(start,next-1));
}
return cache[start]=ret;
}
private static int classify(int start,int next)
{
String M=input.substring(start,next+1);

//모든 숫자가 같을 때
for(int i=0;i<M.length()-1;i++){
if(M.charAt(i)!=M.charAt(i+1))
break;
if(i==M.length()-2)
return 1;
}

//1단조 증가하거나 감소할 때
boolean check=true;
for(int i=0;i<M.length()-1;i++){
if(M.charAt(i)-M.charAt(i+1)!=M.charAt(0)-M.charAt(1))
check=false;
}
if(check==true && Math.abs(M.charAt(1)-M.charAt(0))==1)
return 2;
//두수가 번갈아 등장 할 때
boolean alternating=true;
for(int i=0;i<M.length();i++)
{
if(M.charAt(i)!=M.charAt(i%2))
alternating=false;
}
if(alternating)return 4;
if(check==true)return 5;

return 10;
}

}