동적 계획법 - 원주율 외우기

메모이제이션의 적용

완전 탐색으로 이 문제를 해결하기는 불가능하다. 하지만 적절한 완전 탐색 알고리즘을 만들고 메모이제이션으로 시간을 줄여주면 해결할 수 있다. 이 문제를 푸는 완전 탐색 알고리즘은 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어보며 그 중 난이도의 합이 가장 작은 조합을 찾아낸다.

각 재귀 함수는 한 번 불릴 때마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 재귀적으로 쪼갠다.
나머지 수열의 최적해를 구할 때 앞의 부분을 어떤 시그로 쪼갰는지는 중요하지 않다 (최적 부분 구조가 성립)

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream> 
#include <algorithm> 
#include <stdlib.h> 
#include <vector> 
#include <queue> 
#include <string>
#include <cstring> 
#include <stack> 
#include <map> 
#include <set> 
#include <cmath> 
#define INF 987654321 
#define ENDL cout << endl; 
#define endl '\n' #define swap(type, x, y) do{type t=y;y=x;x=t;}while(0) 

using namespace std; 

typedef long long ll; 
typedef pair<int, int> pl; 

string N; 
int cache[10003]; 

int classify(int a, int b) { 
	string M = N.substr(a, b - a + 1); 
    if (M == string(M.size(), M[0])) 
    	return 1; 
    bool progressive = true; 
    for (int i = 0; i < M.size() - 1; i++) 
    	if (M[i + 1] - M[i] != M[1] - M[0]) 
        	progressive = false; 
    if (progressive && abs(M[1] - M[0]) == 1) return 2; 
    bool alternating = true; 
    for (int i = 0; i < M.size(); i++) 
    	if (M[i] != M[i % 2]) alternating = false; 
    if (alternating) return 4; 
    if (progressive) return 5; 
    return 10; 
} 
int memorize(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(ret, memorize(begin + L) + classify(begin, begin + L - 1));
    return ret; 
} 
int main() {
	ios::sync_with_stdio(false); 
    cin.tie(0); 
    
    int testCase;
    cin >> testCase; 
    
    for (int tc = 0; tc < testCase; tc++) { 
    	cin >> N; 
        memset(cache, -1, sizeof(cache)); 
        cout << memorize(0) << endl; 
    } 
return 0; 
}

이 알고리즘에는 최대 n개의 부분 문제가 있고, 각 부분 문제를 해결하는 데 최대 세 개의 부분 문제를 본다.
따라서 위 코드의 시간복잡도는 O(n)이 된다