원주율 외우기

문제

숫자 조각들을 외우는 난이도는 다음과 같다.

   모든 숫자가 같을 때 - 333, 5555 - 난이도 1

   숫자가 1씩 단조 증가하거나 단조 감소할 때 - 23456, 3210 - 난이도 2

     두 개의 숫자가 번갈아가며 나타날 때 - 323, 54545 - 난이도 4

     숫자가 등차수열을 이룰 때 147, 8642 - 난이도 5

     이 외의 모든 경우 - 난이도 10

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 세 자리에서 다섯 자리까지 끊어 읽고 싶다.

최소의 난이도를 계산하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(1~50)가 주어진다.

그 후 C 줄에 하나씩 각 테스트 케이스가 주어진다.

테스트 케이스는 8자리 이상 10,000 자리 이하의 자연수이며 맨 앞자리가 0일 수도 있다.

예제 입력 및 출력

입력

5

12341234

11111222

12122222

22222222

12673939

 

출력

4

2

5

2

14

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int Case;

class PI {
private:
	string number; //숫자
	int cache[100001]; //시작값에서의 난이도를 저장할 배열
public:
	PI() {
		//생성과 동시에 캐시값 -1로 초기화
		memset(cache, -1, sizeof(cache)); 
	}
	void setNumber() {
		cin >> number;
	}
	//레벨구하는 함수
	int checkLevel(int start, int finish) {
		int i;
		bool flag = true;
		//모든 글자가 같을 때
		for (i = start; i < finish; i++) {
			if (number[i] != number[i + 1])
				flag = false;
		}
		if (flag == true)
			return 1;

		//두개의 숫자가 번갈아가며 나타날때
		flag = true;
		for (i = finish; i >= finish - 2; i--) {
			if (number[finish] != number[finish - 2])
				flag = false;
		}
		if (flag == true)
			return 4;

		//등차수열 일때
		flag = true;
		int common;
		common = number[start + 1] - number[start]; //공차
		for (i = start + 1; i < finish; i++) {
			if (number[i + 1] - number[i] != common)
				flag = false;
		}
		if (flag == true) {
			//공차가 1 또는 -1일때
			if (common == -1 || common == 1)
				return 2;
			//공차가 1이아닌 등차수열
			else return 5;
		}
		return 10; //아무것도 아닌 경우 10
	}
    
	//전체 암기 난이도를 구하는 함수
	int checkDifficulty(int start) {
		int minimum = 9999, level3 = 9999, level4 = 9999, level5 = 9999;

		//기저사례-현재 기준에서 난이도가 이미 계산되었으면 반환
		if (cache[start] != -1) return cache[start];

		//함수 탈출 조건 - 끝에 도달하면 0 반환
		if (start == number.size())
			return 0;

		//현재 기점에서 길이 3, 4, 5일때의 난이도를 모두 계산
		//길이 3일때 레벨
		if (start + 2 < number.size())
			level3 = checkLevel(start, start + 2) + checkDifficulty(start + 3);
		//길이 4일때 레벨
		if (start + 3 < number.size())
			level4 = checkLevel(start, start + 3) + checkDifficulty(start + 4);
		// 길이 5일때 레벨
		if (start + 4 < number.size())
			level5 = checkLevel(start, start + 4) + checkDifficulty(start + 5);

		// 길이 3,4,5중 최소레벨을 찾음
		minimum = min(level3, level4);
		minimum = min(minimum, level5);

		//현재기점 캐시에다 최솟값을 저장
		cache[start] = minimum;
		//수열의 끝이 아니고 더이상 3,4,5로 쪼갤수 없는 경우 9999를 반환하면 최솟값이 될 수 없다.
		return cache[start];
	}
};

PI* mycase;

int main() {
	cin >> Case; //케이스 입력

	mycase = new PI[Case];

	for (int i = 0; i < Case; i++)
		mycase[i].setNumber();

	for (int i = 0; i < Case; i++)
		cout << mycase[i].checkDifficulty(0) << endl;
}

문제 풀이

1. cache값 설정

   - cache[start]: 원주율의 start번 문자부터 원주율을 외우는 난이도의 최솟값을 저장

 

2. 기저 사례

   - cache[start]값이 저장되어있으면 더 이상 난이도 최솟값 구할 필요 없이 cache값 바로 반환

 

3. 함수 탈출 조건

   - 함수의 인자로 전달된 start값이 원주율 문자열 길이와 같다면 끝에 도달했으므로 0 반환 -> 0을 반환하여도 전체 난이도에 영향 X

 

4. 점화식

   - 원주율은 각각 3, 4, 5개씩 끊어서 암기할수 있다.

   - 초기 start값 0이 전달되면 0에서 3, 4, 5로 끊어서 다음 재귀 함수를 호출한다.

   - 각각의 재귀 함수에서 다시 3, 4, 5로 끊어 재귀함수를 호출하며 문자열의 끝까지 도달한다.

   - 함수의 끝에 도달하면 3, 4, 5로 끊어서 호출했던 재귀함수 중 난이도의 최솟값을 cache값에 저장하여 반환하며 원복 한다.