[알고리즘 스터디] 알고스팟 #PI

문제 

알고리즘 문제해결 전략 8단원 문제. 원주율 외우기 

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

algospot.com :: PI

입력된 수열은, 3-5자리씩 끊어서 난이도를 평가한다. 

난이도를 평가하는 기준은 다음과 같다. 

1. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
2. 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
3. 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
4. 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
5. 그 외의 경우 난이도: 10

어떠한 수열을 입력했을 때, 가능한 난이도의 최솟값을 구하면 된다. 

예를들어, 8자리의 수열은 5-3, 4-4, 3-5자리로 나누어 난이도를 계산 할 수 있다. 이 경우의 수들 중에 가장 낮은 난이도를 가지는 경우의 난이도를 구하면 되는 것이다. 

 

입력

C (testcase 개수)

C줄에 걸쳐 8-10000자리의 수열이 입력된다. 

 

출력

각 수열의 최소 난이도.

 

풀이

 

DP와 재귀를 함께 이용하였다. 

basecase

1) 수열의 길이가 3-5 사이일 때

2) cache[start]의 값이 존재할 때

 

코드 

#include <stdio.h> 
#include <iostream> 
#include<cstring>
#include<string> 
#include <limits.h> 
#include <algorithm>
using namespace std;

char arr[10001];
int cache[10001];
int recursive(int start, int len) {
	int result;
	int& ret = cache[start];
	if (ret != 0) {
		return ret;
	}
	if (len >= 3 && len <= 5) { //끝부분 일 때 
		char before, after;
		int dif[4];
		int score = 0;
		bool flag[4] = { 1,1,1,1 };
		before = arr[start];
		for (int i = 1;i < len;i++) {
			after = arr[start + i];
			if (before != after) //다른 숫자가 나오면 난이도 1 탈락 
				flag[0] = 0;
			dif[i - 1] = before - after;
			if (dif[i - 1] != 1 && dif[i - 1] != -1) 
				flag[1] = 0;
			if (i >= 2) { 
				if (dif[i - 2] != dif[i - 1]) { // 등차수열 x
					flag[1] = 0;
					flag[3] = 0;
				}
			}
			if (arr[start+(i % 2)] != after) //숫자 두개가 번갈아 나오는 경우 
				flag[2] = 0;
			before = after;
		}
		for (int i = 0;i < 4;i++) {
			if (flag[i] == 1) {
				if (i == 0)
					score = 1;
				else if (i == 1) 
					score = 2;
				else if (i == 2)
					score = 4;
				else if (i == 3)
					score = 5;
				break;
			}
		}
		if (score == 0)
			score = 10;
		return score;
	}

	char before, after;
	int dif[4];
	int score[3] = { 0,0,0 };
	bool flag[4];
	before = arr[start];
	//앞부터 3,4,5 난이도 계산해야함 
	for (int k = 3;k <= 5;k++) {
		before = arr[start];
		bool flag[4] = { 1,1,1,1 };
		for (int i = 1;i < k;i++) {
			after = arr[start + i];
			if (before != after) //다른 숫자가 나오면 난이도 1 탈락 
				flag[0] = 0;
			dif[i - 1] = before - after;
			if (dif[i - 1] != 1 && dif[i - 1] != -1) 
				flag[1] = 0;
			if (i >= 2) {
				if (dif[i - 2] != dif[i - 1]) { // 등차수열 x
					flag[1] = 0;
					flag[3] = 0;
				}
			}
			if (arr[start+(i % 2)] != after) //숫자 두개가 번갈아 나오는 경우 x
				flag[2] = 0;
			before = after;
		}
		for (int i = 0;i < 4;i++) {
			if (flag[i] == 1) {
				if (i == 0)
					score[k-3] = 1;
				else if (i == 1)
					score[k-3] = 2;
				else if (i == 2)
					score[k-3] = 4;
				else if (i == 3)
					score[k-3] = 5;
				break;
			}
		}
		if (score[k-3] == 0)
			score[k-3] = 10;
	}
	result = INT_MAX;
	if (len >= 6)
		result = min(recursive(start + 3, len - 3)+score[0],result);
	if (len >= 7) 
		result = min(recursive(start + 4, len - 4) + score[1], result);
	if (len >= 8)
		result = min(recursive(start + 5, len - 5)+score[2],result);
	ret = result;
	return result;
}
int main() {
	int C,len;
	scanf_s("%d\n", &C);
	string s;
	for (int c = 0;c < C;c++) {
		getline(cin, s);
		len = s.size();
		fill(cache, cache + len, 0);
		strcpy_s(arr, s.c_str());
		int result = recursive(0, len);
		printf("%d\n", result);
	}
}

입력 받는것도 꽤 어려웠다. 

각 testcase별로 수열의 길이를 따로 입력하는 것이 아니기 때문에, int배열이 아니라 string을 이용해서 입력 받았다. 

 

제출 결과