[Week 3] PI self review - hanjuuuuuu

[hanjuuuuuu]

PI self review

1. 해결 시도 과정

3~5글자씩 각각 끊어서 재귀함수로 3으로 끊은 경우, 4로 끊은 경우, 5로 끊은 경우 각각을 비교하고 최소 난이도 값을 구하려고 하였습니다.

2. 아이디어

완전탐색으로 재귀함수를 이용하여 최소 난이도의 합을 구하고자 하였습니다.
메모이제이션은 책을 참고했습니다.

3. 코드 설명

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 987654321;
int mins = 0;		//최소의 난이도
int cache[10001];		
string N;

int type(int a, int b) { //난이도. 원주율을 가져와 계산.
	string m = N.substr(a, b - a + 1);

	bool same = true;
	for (int i = a; i < b; i++) {
		if (m[i + 1] - m[i] != 0)				//모든 숫자가 같을 때
			same = false;
	}
	if(same)
		return 1;

	bool one = true;
	for (int i = a; i < b; i++) {
		if (m[i + 1] - m[i] != 1)		//숫자가 1씩 단조증가할 떄
			one = false;
	}
	for (int i = a; b; i++) {
		if (m[i] - m[i + 1] != 1)		//숫자가 1씩 단조감소할 때
			one = false;
	}
	if (one)
		return 2;

	bool chg = true;
	for (int i = a; i < b; i++) {
		if (m[i] != m[i % 2])			//두개의 숫자가 번갈아가며 출현할 때
			chg = false;
	}
	if (chg)
		return 4;

	bool seq = true;
	for (int i = a; i < b; i++) {
		if (m[i + 1] - m[i] != m[1] - m[0])	//숫자가 등차수열을 이룰 때
			seq = false;
	}		
	if (seq)
		return 5;

	//그 외의 경우
	return 10;

	}
int pi(int a) {
	if (a == N.size())		//끝까지 다 돌은 경우
		return 0;
	
	//메모이제이션
	int ret = cache[a];
	if (ret != -1)
		return ret;
	ret = INF;
	for (int L = 3; L <= 5; L++) {
		if (a + L <= N.size())
			ret = min(ret, pi(a + L) + type(a, a + L - 1));
	}
        return ret;


}

int main() {
	int C;
	cin >> C;
	for (int i = 0; i < C; i++) {
		memset(cache, -1, sizeof(cache));
		cin >> N;
		cout << pi(0) << endl;
	}

	return 0;
}

substr로 원주율의 부분을 가져와 모든 난이도를 for문을 돌며 계산하는 방법으로 구현했습니다.
메모이제이션을 이용해 최소값을 저장하고 반환할 수 있었습니다.

4. 막힌 점 및 개선 사항

난이도 계산 시 반복문을 많이 돌게 끔 코드를 작성하여 시간초과가 발생한 것 같습니다.
조금 더 시간을 줄일 수 있게끔 코드의 효율성을 고려해야 할 듯 합니다.