PI(원주율 외우기)

(출처) https://algospot.com/judge/problem/read/PI

완전탐색의 경우

문제의 입력으로 올 수 있는 숫자 문자열의 최대 길이는 1만이고, 이 1만 개의 숫자를 앞에서부터 3개씩 자를지 or 4개씩 자를지 or 5개씩 자를지, 총 3가지 선택지 중 하나를 택하여 숫자가 모두 분할이 될 때까지 반복해 나가야 한다. 따라서 경우의 수는 최대한 적게 어림잡아 계산하여도 3^2000개가 넘는다. 이래서는 완전탐색으로 문제를 해결할 수 없고 다른 방법을 생각해야 한다.

메모이제이션

따라서 1만 개의 숫자 각 요소마다 해당 요소에서부터 만들 수 있는 최소 난이도 값을 cache화 하여 답을 구해보고자 생각했다.

cache[index] = min (3개의 난이도 + cache[index+3], 4개의 난이도 + cache[index+4], 5개의 난이도 + cache[index+5])

위와 같은 경우라면 부분문제는 총 1만이 만들어지고 각 부분문제는 상수시간만의 계산 시간이 필요하게 되므로 O(N)의 시간복잡도 만으로 해결할 수 있다고 판단했다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
string num;
int cache[10000];
int INF = numeric_limits<int>::max() - 100000;

int cal_difficulty(string num) {
	int differ_before = (int) num[1] - (int) num[0] ;
	int first = (int) num[0] - 48;
	bool sequence = true;
	bool alter = true;

	for (int i = 1; i < num.size() - 1; i++) {
		int current = (int) num[i] - 48;
		int next = (int) num[i + 1] - 48;
		int differ_current = next - current;

		if (differ_before != differ_current) {
			sequence = false;
		}
		if (first != next) alter = false;
		differ_before = differ_current;
		first = current;
	}

	if (sequence) {
		if (differ_before == 0) return 1;
		else if (differ_before == -1 || differ_before == 1) return 2;
		else return 5;
	}
	if (alter) return 4;

	return 10;
}

int pi(int index) {
	//예외처리
	if (index == num.size()) return 0;
	if (index > num.size() - 3) return INF;
	
	//메모이제이션
	int& ret = cache[index];
	if (ret < INF) return ret;
	
	ret = min(cal_difficulty(num.substr(index, 4)) + pi(index + 4), cal_difficulty(num.substr(index, 3)) + pi(index + 3));
	ret = min(ret, cal_difficulty(num.substr(index, 5)) + pi(index + 5));

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		cin >> num;
		fill_n(cache, 10000, INF);
		int ret = pi(0);
		cout << ret << "\n";
	}
	return 0;
}

기억하고 싶은 점

여태까지 메모이제이션 cache 배열을 초기화할 때 memset 함수를 이용했다. 따라서 이번 문제도 memset을 이용하여 배열을 초기화하고자 했는데 자꾸 내가 넘겨준 값이 아닌 이상한 값으로 배열이 초기화 돼버리는 현상이 발생했다.

그래서 이유를 한 번 찾아보니 memset 함수의 경우 인자로 전해 받은 메모리주소에 전해준 크기만큼 1바이트 단위로 끊어가며 각 바이트마다 내가 념겨준 값을 덮어 씌우는 함수였다는 것을 알게 되었다.

기존에 문제를 풀 때는 항상 -1로 값을 초기화했기 때문에 1바이트 단위로 모든 메모리주소를 -1로 채워도 결국은 배열에 -1이 남게 되므로 정상적으로 초기화가 된 것처럼 보였던 것뿐이었다. 이번에는 -1이 아닌 양의 정수를 memset으로 초기화 할려고 하니까 문제가 표면에 드러나게 된 것.

따라서 이번에는 더 느리지만 확실하게 값을 초기화 시켜줄 수 있는 fill 함수를 이용했다.

이번에는 문제가 쉽기도 했고 구현하는 데 재미를 느낄만한 요소가 있던지라 나름 재미있게 푼 문제였던 것 같다.