알고리즘 문제해결전략 문제8.7 원주율 외우기 (ID: PI)

[문제 링크]

algospot.com :: PI

---

비교 연산자가 많고 복잡해서 잔실수들을 고치느라 시간이 오래걸린 문제였다.

 

세 자리에서 다섯 자리까지로 끊어서 읽기 때문에 나올 수 있는 경우의 수는 한정되어 있다.

세 자리부터 다섯 자리까지 끊어서 읽을 수 있는 모든 경우의 수에 대하여 나올 수 있는 난이도의 합이 최소가 되는 값을 찾아주면 된다.

마지막에 남는 자리수가 2개 이하라면 잘못 끊어서 읽은 것이기 때문에 불가능(INF)값을 리턴한다.

 

추가로 PI[start]가 가질 수 있는 최소 난이도는 항상 같으므로 메모이제이션을 적용하면 제한시간 안에 문제를 풀 수 있다.

---

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int INF = 987654321;
int memo[10001], digit;
string PI;

inline int min(const int a, const int b) { return a < b ? a : b; }

int Solution(int start)
{
	if (start == digit) return 0;

	int& ret = memo[start];
	if (ret != -1) return ret;

	ret = INF;

	if (start + 2 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';

		if (a == b && b == c)
			ret = min(ret, Solution(start + 3) + 1);

		else if ( (b == a + 1 && c == b + 1) || 
				  (b == a - 1 && c == b - 1) )
			ret = min(ret, Solution(start + 3) + 2);

		else if (a == c && a != b)
			ret = min(ret, Solution(start + 3) + 4);

		else if (a - b == b - c)
			ret = min(ret, Solution(start + 3) + 5);

		else
			ret = min(ret, Solution(start + 3) + 10);
	}

	if (start + 3 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';
		int d = PI[start + 3] - '0';

		if (a == b && b == c && c == d)
			ret = min(ret, Solution(start + 4) + 1);

		else if ( (b == a + 1 && c == b + 1 && d == c + 1) || 
				  (b == a - 1 && c == b - 1 && d == c - 1) )
			ret = min(ret, Solution(start + 4) + 2);

		else if (a == c && b == d)
			ret = min(ret, Solution(start + 4) + 4);

		else if (a - b == b - c && b - c == c - d)
			ret = min(ret, Solution(start + 4) + 5);

		else
			ret = min(ret, Solution(start + 4) + 10);
	}

	if (start + 4 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';
		int d = PI[start + 3] - '0';
		int e = PI[start + 4] - '0';

		if (a == b && b == c && c == d && d == e)
			ret = min(ret, Solution(start + 5) + 1);

		else if ((b == a + 1 && c == b + 1 && d == c + 1 && e == d + 1) || 
				 (b == a - 1 && c == b - 1 && d == c - 1 && e == d - 1))
			ret = min(ret, Solution(start + 5) + 2);

		else if (a == c && a == e && b == d)
			ret = min(ret, Solution(start + 5) + 4);

		else if (a - b == b - c && b - c == c - d && c - d == d - e)
			ret = min(ret, Solution(start + 5) + 5);

		else
			ret = min(ret, Solution(start + 5) + 10);
	}

	return ret;
}
int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> PI;
		digit = PI.size();

		cout << Solution(0) << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 53 day