AlgoSpot) PI

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

DP를 이용해서 최소비용으로 조각들을 설정하는 방법에 대해 다룬 문제입니다.

최소 3개에서 최대 5개의 부분조각을 가질수있으며 부분조각들의 패턴에 따라 비용이 결정되는 함수를 생성하고

cache배열에 최소비용을 저장하는 방식으로 dp를 이용해서 문제를 해결했습니다.

코딩을 하던중 책에서 string(temp.size(), temp[0]) 함수를 찾아서 이용했습니다.

string(size_t c, char c)함수는 c를 n개 채우는 함수입니다.

#include 
#include 
#include 
#include 

using namespace std;

string N;
const int INF = 987654321;
int cache[10001];

int classify(int a, int b) { // 몇개가 연속되는지 알아내느 함수
	string temp = N.substr(a, b - a + 1);
	
	if (temp == string(temp.size(), temp[0])) return 1; // 첫글자로 이루어진 문자와 같으면 1

	bool check = true; // 단조 증가 or 감소
	for (int i = 0; i < temp.size() - 1; i++) {
		if (temp[i + 1] - temp[i] != temp[1] - temp[0]) {
			check = false;
			break;
		}
	}
	
	if (check && abs(temp[1] - temp[0]) == 1) return 2; // 단조 증가 or 감소일 경우

	bool alter = true;

	for (int i = 0; i < temp.size(); i++) {
		if (temp[i] != temp[i % 2]) {
			alter = false;
			break;
		}
	}

	if (alter) return 4; // 차례로 나올경우

	if (check) return 5; // 등차수열일 경우

	return 10;
}

int Pi(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, Pi(begin + L) + classify(begin, begin + L - 1));
		}
	}
	return ret;
}

int main() {
	std::ios::sync_with_stdio(false);
	int C;
	//freopen("text.txt", "r", stdin);
	cin >> C;

	while (C--) { // 케이스 시작
		cin >> N;
	
		memset(cache, -1, sizeof(cache));
		
		cout << Pi(0) << endl;	
	}
	
	return 0;
}