8.7_원주율 외우기_PI

문제 설명

algospot.com :: PI

• 8글자 이상 10000글자 이하의 숫자가 주어진다
• 그 숫자를 3글자에서 5글자로 끊어서 외운다고 한다.
• 끊어진 조각의 암기 난이도를 다음과 같다고 한다.
  • 모든 숫자가 같을 때 : 난이도 1
  • 숫자가 1씩 단조 증가하거나 단조 감소할 때 : 난이도 2
  • 두 개의 숫자가 번갈아가며 출현할 때 : 난이도 4
  • 숫자가 등차 수열을 이룰 때 : 난이도 5
  • 그 외의 경우 : 난이도 10

=> 주어진 숫자를 끊어 외우는 난이도의 합 중 최솟값을 출력하기

 

 

문제 풀이

우선 문제에서 주어진대로

해당 위치에서 3자리, 4자리, 5자리로 끊은 후 해당 조각의 난이도를 구하고

이렇게 숫자 끝까지 탐색한 후 얻어지는 난이도의 합의 최솟값을 출력하도록 했다.

 

하지만 이렇게만 구현하면 시간초과가 발생한다.

 

1번 경우 : 0인덱스-3자리 -> 3인덱스-3자리 -> 6인덱스-3자리 -> 9인덱스-...

2번 경우 : 0인덱스-5자리 -> 5인덱스-4자리 -> 9인덱스-...

 

위와 같은 경우로 탐색을 할 때, 9인덱스 부터는 1번 경우에서 이미 했던 연산을 2번 경우에서 똑같이 수행하게 된다.

 

해당 인덱스에서 연산한 결과를 저장해두고 사용하면,

즉, 메모이제이션을 이용하면 중복 연산을 줄일 수 있다.

 

이에 indexLevels[10000][3] 라는 배열을 생성하여

각 인덱스에서 3글자 탐색결과, 4글자 탐색결과, 5글자 탐색결과를 저장하도록 했다.

 

문제 풀이 코드

#include <iostream>
#include <string.h>

using namespace std;

int memoization[10000];
int indexLevels[10000][3];	// 0: 3글자, 1: 4글자, 2: 5글자
char numArr[10000];
int length;

int min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

// index에서 시작, size만큼의 길이인 문자열의 level 구하기
int getIndexLevels(int index, int size) {
	bool flag = true;
	for (int i = index; i < index + size - 1; ++i) {	// 1번 경우
		if (numArr[i] != numArr[i + 1]) {
			flag = false;
			break;
		}
	}
	if (flag) {
		return 1;
	}
	
	int diff = numArr[index] - numArr[index + 1];
	if (diff == 1 || diff == -1) {	// 2번 경우
		flag = true;
		for (int i = index; i < index + size - 1; ++i) {
			if (numArr[i] - numArr[i + 1] != diff) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return  2;
		}
	}

	if (numArr[index] == numArr[index + 2]) {	// 3번 경우
		flag = true;
		for (int i = index; i < index + size - 2; ++i) {
			if (numArr[i] != numArr[i + 2]) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return 4;
		}
	}

	if (diff == numArr[index + 1] - numArr[index + 2]) {	// 4번 경우
		flag = true;
		for (int i = index; i < index + size - 1; ++i) {
			if (numArr[i] - numArr[i + 1] != diff) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return 5;
		}
	}

	return 10;
}

int getMinLevel(int index) {
	if (index >= length)
		return 0;

	int& ret = memoization[index];
	if (ret != -1)
		return ret;

	// 3글자, 4글자, 5글자
	int size3 = indexLevels[index][0] + getMinLevel(index + 3);
	int size4 = indexLevels[index][1] + getMinLevel(index + 4);
	int size5 = indexLevels[index][2] + getMinLevel(index + 5);

	return ret = min(min(size3, size4), size5);
}

int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		memset(numArr, '\0', 10000);
		memset(memoization, -1, sizeof(int) * 10000);
		memset(indexLevels, 20, sizeof(int) * 10000 * 3);	// 최대 난이도는 10이므로, 나올 가능성이 없는 숫자 20으로 초기화
		cin >> numArr;
		length = 0;
		while (numArr[length] != '\0') ++length;
		
		for (int size = 3; size <= 5; ++size) {
			for (int index = 0; index <= length - size; ++index) {
				indexLevels[index][size - 3] = getIndexLevels(index, size);
			}
		}

		int result = getMinLevel(0);
		cout << result << endl;
	}
	return 0;
}