[algospot][DP] 원주율 외우기 : https://algospot.com/judge/problem/read/PI

PI.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<limits.h>
#define L1 1
#define L2 2
#define L3 4
#define L4 5
#define L5 10
using namespace std;

/*
 * 시간복잡도 : O(N) (N = |s|)
 */

vector<int> dp;
string s;

int getLevel(string s) {
	
	int size = s.size();
	int diff1 = s[1] - s[0];
	int diff2 = s[2] - s[1];
	char num[2] = { s[0], s[1] };
	int level = L5;

	if (diff1 == diff2) {
		if (diff1 == 0) level = L1;
		else if(diff1 == -1 || diff1 == 1) level = L2;
		else level = L4;
	}

	for (int i = 2; i < size; i++) {
		int diff = s[i] - s[i - 1];
		if (diff != diff1) {
			level = L5;
			break;
		}
	}
	if (level == L5) {
		bool isL3 = true;
		for (int i = 2; i < size; i++) {
			if (s[i] == num[i % 2]) continue;
			isL3 = false; break;
		}
		if (isL3) return L3;
	}

	return level;
}

// s[ind~] 최소 난이도
int solve(int ind) {
	if (s.size() == ind) return 0;

	int& ret = dp[ind];
	if (ret != -1) return ret;
	ret = 1e9; // if don't have enough length(more than 3) -> Impossible

	// [ind, nextInd)
	for (int nextInd = ind + 3; nextInd <= min(ind + 5, (int)s.size()); nextInd++) {
		ret = min(ret, getLevel(s.substr(ind, nextInd - ind)) + solve(nextInd));
	}
	return ret;
}

int main() {
	int C;
	cin >> C;
	while (C--) {
		cin >> s;
		dp = vector<int>(s.size(), -1);
		cout << solve(0) << endl;
	}
	return 0;
}