[Week 3] PI self review - Yunhyunjo

[Yunhyunjo]

PI self review

• 파일명: PI/Yunhyunjo.cpp
• 수행시간: 728ms

1. 문제 해결 과정

3,4,5개씩 각각 다 한번씩 계산한 다음 가장 작은 수를 return하면 될것이라고 생각했습니다. 그렇게 해서 처음엔 시간초과가 나고 메모이제이션을 통해 해결을 했지만 그래도 시간이 꽤 걸리기 때문에 레벨 계산 부분을 좀 더 수정해 보고 입출력 시간을 줄여봐야 할 것 같습니다.

2. 아이디어

3,4,5로 잘라 현재 레벨을 계산하고 다음 나머지들은 재귀 호출을 통해 다시 또 계산했습니다. 이미 한 번 했던 계산은 저장해 두고, 만약 잘라야 하는 숫자보다 적게 남을 시에는 큰 값을 미리 저장해두어 그걸로 계산했습니다.

3. 코드 설명

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string s;
int startArr[10000]; // 시작하는 위치에서의 작은 값 저장
int levelArr[10000][3];  // 난이도값 저장
int minLevel(int start);
int currentLevel(int len, int start);
int oneLevel(int len, int start);
int twoLevel(int len, int start);
int fourLevel(int len, int start);
int fiveLevel(int len, int start);

int main(void) {
	int n;

	cin >> n;
	while (n--)
	{
		cin >> s;
		fill(startArr, startArr + 10000, 0);
		for (int i = 0; i<10000; i++)
			fill(levelArr[i], levelArr[i] + 10000, 0);
		cout << minLevel(0) << "\n";
	}
}

int minLevel(int start) {  // 최소 난이도를 구하는 함수
	int size = s.size() - start, three = 999999999, four = 999999999, five = 999999999;  // 미리 큰 값을 저장
	if (size == 0)
		return 0;
	if (startArr[start] != 0)       // 값이 저장이 되어있으면 계산하지 말고 return
		return startArr[start];

	if (size > 2)
		three = currentLevel(3, start) + minLevel(start + 3);  // 3개씩 끊을 때
	if (size > 3)
		four = currentLevel(4, start) + minLevel(start + 4);   // 4개씩 끊을 때
	if (size > 4)
		five = currentLevel(5, start) + minLevel(start + 5);   // 5개씩 끊을 때

	int min = (three < four) ? three : four;                  
	startArr[start] = (min < five) ? min : five;               // 셋 중 가장 작은 값 비교 후 저장
	return startArr[start];
}

int currentLevel(int len, int start) {   // 난이도를 계산하는 함수
	if (levelArr[start][len - 3] != 0)
		return levelArr[start][len - 3];
	if (oneLevel(len, start))
		return 1;
	else if (twoLevel(len, start))
		return 2;
	else if (fourLevel(len, start))
		return 4;
	else if (fiveLevel(len, start))
		return 5;
	else {
		levelArr[start][len - 3] = 10;
		return 10;
	}
}

int oneLevel(int len, int start) {  // 난이도 1
	int first = s[start] - 48;
	for (int i = start + 1; i < start + len; i++) {
		if (s[i] - 48 != first)
			return 0;
	}
	levelArr[start][len - 3] = 1;
	return 1;
}

int twoLevel(int len, int start) { // 난이도 2
	int a;
	if ((s[start] - 48) - (s[start + 1] - 48) == 1)
		a = -1;
	else if ((s[start] - 48) - (s[start + 1] - 48) == -1)
		a = 1;
	else
		return 0;
	for (int i = start + 1; i < start + len; i++) {
		if (s[i] - 48 == (s[i - 1] - 48) + a)
			continue;
		else
			return 0;

	}
	levelArr[start][len - 3] = 2;
	return 1;
}

int fourLevel(int len, int start) {  // 난이도 4
	int first = s[start] - 48;
	int second = s[start + 1] - 48;
	if (first == second)
		return 0;
	for (int i = start + 2; i < start + len; i++) {
		if (s[i] - 48 != s[i - 2] - 48)
			return 0;
	}
	levelArr[start][len - 3] = 4;
	return 1;
}

int fiveLevel(int len, int start) {  // 난이도 5
	int d = (s[start + 1] - 48) - (s[start] - 48);
	for (int i = start; i < start + len - 1; i++) {
		if ((s[i] - 48) + d != s[i + 1] - 48)
			return 0;
	}
	levelArr[start][len - 3] = 5;
	return 1;
}

난이도 1,2,4,5를 계산하는것을 다 구현하고 재귀호출을 통해 다음 나머지 문자열의 난이도를 계산했습니다.