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

문제 : 원주율 외우기 (난이도 : 下)

 

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

 

 분석

조각의 길이가 3, 4, 5 중 하나이므로 다음과 같이 생각해보자.

 

1. 길이가 3인 조각 난도 + 3글자 뺀 나머지 수열에 대한 최적해

2. 길이가 4인 조각 난도 + 4글자 뺀 나머지 수열에 대한 최적해

3. 길이가 5인 조각 난도 + 5글자 뺀 나머지 수열에 대한 최적해

 

시작 위치가 주어졌을 때 최소 난도를 반환하는 함수를 memorize(begin),

주어진 구간([a, b])의 난도를 반환하는 함수를 classify(a, b)라 하자.

 

 구현

const int INF = 987654321;
string input;

//input[a, b] 구간의 난도를 반환한다.
//난도를 판단하는 if문 눈에 익혀두자.
int classify(int a, int b)
{
	//조각
	string piece = input.substr(a, b - a + 1);
	//난도 1
	if (piece == string(piece.size(), piece[0])) return 1;
	//등차수열; 공차 +-1 -> 난도 2, else -> 난도 5
	bool progressive = true;
	int d = piece[1] - piece[0];
	for (int i = 0; i < piece.size() - 1; i++)
	{
		if (piece[i + 1] - piece[i] != d)
		{
			progressive = false;
		}
	}
	if (progressive)
	{
		if (abs(d) == 1) return 2;
		return 5;
	}
	//난도4
	bool alter = true;
	for (int i = 0; i < piece.size(); i++)
	{
		if (piece[i] != piece[i%2])
		{
			alter = false;
		}
	}
	if (alter) return 4;
	//else 난도 10
	return 10;
}

int cache[10002];
int memorize(int begin)
{
	//base case; 수열의 끝에 도달했을 경우
	if (begin == input.size()) return 0;
	//memoization
	int& ret = cache[begin];
	if (ret != -1) return ret;
	ret = INF;
	for (int L = 3; L <= 5; L++)
	{
		if (begin+L <= input.size())
		{
			ret = min(ret, memorize(begin + L) + classify(begin, L + begin - 1));
		}
	}
	return ret;
}


int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		cin >> input;
		cout << memorize(0) << '\n';
	}
	return 0;
}