[Algorithm] 🥧원주율 외우기

0. 문제

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


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


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


모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
그 외의 경우 난이도: 10
원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

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

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

1. 아이디어

L글자 제외 나머지 수열에 대한 난이도 + 길이 L인 조각의 난이도 (L은 3-5)
메모이제이션

2. 핵심 풀이

1) L글자 제외 나머지 수열에 대한 난이도 + 길이 L인 조각의 난이도 (L은 3-5)

ret = Math.min(ret, memorize(begin+L) + classify(begin, begin+L-1));

2) 메모이제이션

int ret = cache[begin];
if(ret != -1) return ret;
...		
return ret;

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class DP_EX_6 {
	static String N;
	static int cache[];
	static int max = 12345678;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int tc = Integer.parseInt(br.readLine().trim());
		
		while(tc > 0) {
			N = br.readLine().trim();
			cache = new int[N.length()];
			
			Arrays.fill(cache, -1);
			
			bw.flush();
			bw.write(memorize(0)+"\n");
			tc--;
		}
		
		bw.close();
	}
	
	static int classify(int a, int b) {
		String M = N.substring(a, b+1);
		String s = "";
		
		for(int i=0; i<M.length(); i++)
			s += M.charAt(0);
		
		if(M.equals(s)) return 1;
		
		boolean progressive = true;
		for(int i=1; i<M.length(); i++) {		
			if(M.charAt(i)-M.charAt(i-1) != M.charAt(1)-M.charAt(0)) {
				progressive = false;
				break;
			}
		}
		

		if(progressive && Math.abs(M.charAt(1)-(int)M.charAt(0)) == 1)
			return 2;
		
		boolean alternative = true;
		for(int i=0; i<M.length(); i++) {
			if(M.charAt(i) != M.charAt(i%2)) {
				alternative = false;
				break;
			}
		}
		
		if(alternative) return 4;
		if(progressive) return 5;
		
		return 10;
		
	}
	
	static int memorize(int begin) {
		if(begin == N.length()) return 0;
		
		int ret = cache[begin];
		if(ret != -1) return ret;
		ret = max;
		
		for(int L=3; L<=5; L++) {
			if(begin+L <= N.length())
				ret = Math.min(ret, memorize(begin+L) + classify(begin, begin+L-1));
		}
		
		return ret;
	}
}

4. 결과

시간초과 났는데 테스트 케이스 잘 돌아가는 걸로 봐서는 잘 짠 거 같다..