알고스팟 - 원주율 외우기 (PI) [C++]

 이 문제는 다이나믹 프로그래밍을 이용한 문제이다. 문자열을 3 ~ 5글자씩 끊어서 읽고, 각 읽는 난이도를 모두 더했을 때의 최솟값을 리턴하는 문제이다. 문자열 S를 3글자 끊고 남은 나머지 문자열에 대한 재귀 연산을 수행하는 방식으로 구현했다. 이 때 나머지 문자열을 구하는 문제는 앞의 문제에 의존적이지 않으므로 다이나믹 프로그래밍을 사용할 수 있고, 시작 위치에 대한 값을 dp 배열에 저장함으로써 빠르게 구할 수 있었다.

 

#include <iostream>
#include <string>

using namespace std;

int toNumber(char c) {
	return c - '0';
}

int absolute(int num) {
	if (num < 0) {
		return -num;
	}
	return num;
}

bool diff1(string &input, int start, int end) {
	char c = ' ';
	for (int i = start; i <= end; i++) {
		if (i == start) {
			c = input[i];
			continue;
		}

		if (c != input[i]) {
			return false;
		}
	}

	return true;
}

bool diff2(string &input, int start, int end) {
	int dist = toNumber(input[start + 1]) - toNumber(input[start]);

	if (absolute(dist) != 1) {
		return false;
	}

	for (int i = start; i <= end - 1; i++) {
		if (input[i + 1] - input[i] != input[start + 1] - input[start]) {
			return false;
		}
	}

	return true;
}

bool diff3(string &input, int start, int end) {
	char temp[2];

	temp[start % 2] = input[start];
	temp[(start + 1) % 2] = input[start + 1];

	for (int i = start; i <= end; i++) {
		if (temp[i % 2] != input[i]) {
			return false;
		}
	}

	return true;
}

bool diff4(string &input, int start, int end) {
	for (int i = start; i <= end - 1; i++) {
		if (input[i + 1] - input[i] != input[start + 1] - input[start]) {
			return false;
		}
	}

	return true;
}

int calculate(string &input, int start, int end) {
	if (diff1(input, start, end)) {
		return 1;
	}
	if (diff2(input, start, end)) {
		return 2;
	}
	if (diff3(input, start, end)) {
		return 4;
	}
	if (diff4(input, start, end)) {
		return 5;
	}
	return 10;
}

#define MAX 10000

int dp[MAX];

void init(int size) {
	for (int i = 0; i < size; i++) {
		dp[i] = -1;
	}
}

int solve(string &input, int startIndex) {
	int size = input.size();

	if (startIndex == size) {
		return 0;
	}

	if (dp[startIndex] != -1) {
		return dp[startIndex];
	}
	
	int result = 1000000000;

	if (startIndex + 3 <= size) {
		int present = calculate(input, startIndex, startIndex + 2);

		result = min(result, solve(input, startIndex + 3) + present);
	}

	if (startIndex + 4 <= size) {
		int present = calculate(input, startIndex, startIndex + 3);

		result = min(result, solve(input, startIndex + 4) + present);
	}

	if (startIndex + 5 <= size) {
		int present = calculate(input, startIndex, startIndex + 4);

		result = min(result, solve(input, startIndex + 5) + present);
	}

	return dp[startIndex] = result;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;

	cin >> C;

	for (int test = 0; test < C; test++) {
		string input;

		cin >> input;

		init(input.size());
		int answer = solve(input, 0);

		cout << answer << '\n';
	}

	return 0;
}