원주율 외우기

문제: PI / 동적계획법

원주율을 외운다는 스토리는 뒤로하고 문제의 핵심은 끊어읽는 모든 경우를 어떻게 처리해야할까? 이다.

어떻게 돌아가는지 좀 써보자.

앞에서부터 3을 끊고, 나머지 처리

앞에서부터 4를 끊고, 나머지 처리

앞에서부터 5를 끊고, 나머지 처리

뒷 부분, 나머지 처리들도 마찬가지로 반복된다. 

그런데, 저걸 그때그때 모두 계산하면 너무 오래 걸리잖아? 어차피 중복이 있을 것같단 말이지..

예를들어 8까지 읽었다고 치자. 그러면 처리:남은길이 = 8:N  이 될텐데, 이 조합으로 access할 경우가 있다는 거다.

그러니까 저런 경우는 한 번 계산한걸 저장해두고 써먹자.. 이렇게 해서 쥐어짠 코드는 다음과 같다.

대충 이런 그림..

int fn(string str)
{
	int minCost = INT_MAX;

	if (str.size() == 0) 
		return 0;

	for(int i=3; i<=5; i++) {
		int sz = str.size() - i;
		if (sz >= 3 || sz == 0) {
			string head = str.substr(0, i);
			string tail = str.substr(i, str.size());
			if (cache[head.size()][tail.size()] == 0)
				cache[head.size()][tail.size()] = costFn(head) + fn(tail);

			minCost = min(minCost, cache[head.size()][tail.size()]);
		}
	}

	return minCost;
}

결과는 TLE ㅎㅎㅎ

다른 방법이 있을까? 짱구를 굴리다가 재귀 없이 반복으로 풀어내는 방법을 찾아냈다.

아래 그림과 같이 단계가 지날수록 계산해야 하는 횟수가 늘어나는 방법. 

빨간선처럼 중복되는 경우 최소값으로 업데이트 하도록 진행하면 각 단계가 지날때마다 최소값이 구해진다.

이후에는 6,7,8,9,10 을 방문하면서 계속해서 진행...

int fn(string str)
{
	int size = str.size();
	
	for(int i = 0, step = 1; i < size; i += 3, step++) {
		for(int j = 0; j < step*2-1; j++) {
			for(int k = 3; k <= 5; k++) {
				int remain = size - (i+j+k);
				if (remain >= 3 || remain == 0) {
					if (dp[i+j+k] == 0) {
						dp[i+j+k] = dp[i+j] + costFn(str.substr(i+j, k));
					} else {
						dp[i+j+k] = min(dp[i+j+k], dp[i+j] + costFn(str.substr(i+j, k)));
					}
				}
			}
		}
	}

	return dp[size];
}

돌려보니 느리다. 당연하다. 딱봐도 N^2 인데... (내부에 k는 애교로 봐준다고 쳐도)

문제가 무엇일까? 겹치는 곳을 계속 방문하는 문제가 있다. 

6-10을 방문한 이후에도 다시 9-10을 다음에 반복한다는 것이 문제다. 뭔가가 빠졌는데....

그렇다면 거꾸로 생각해보면 어떨까..? 

3,4,5는 초기값으로 셋팅 해주는데 그 다음부터는 뒤를 돌아보는 것이다.

방향만 바꿔서 생각했을 뿐인데, 각 자리에서 해줘야할 연산은 딱 3회로 줄었다. 유식한척 식으로 써보자!

cost(n) = min(cost(3자리문자열) + cache(n-3), cost(4자리문자열) + cache(n-4), cost(5자리문자열) + cache(n-5))

이거같다. 느낌이 온다. 돌려보니 결과가 좌라락 나온다. (느낌 아니까...)

int fn(string str)
{
	int size = str.size();

	for(int i = 3; i <= 5; i++)
		dp[i] = costFn(str.substr(0, i));

	for(int i = 3; i < size; i += 3) {
		for(int j = 3; j <= 5; j++) {
			int n = i + j;
			if (n > size) break;
			for(int k = 3; k <= 5; k++) {
				if (n - k >= 3) {
					int cost = dp[n-k] + costFn(str.substr(n-k, k));
					if (dp[n] == 0) {
						dp[n] = cost;
					} else {
						dp[n] = min(cost, dp[n]);
					}
				}
			}
		}
	}

	return dp[size];
}

돌려보니 통과다. 머리가 나쁜 덕분에 올바른 설계로 오기까지 꽤 삽질을 많이했다.

느낀점은 똑같은 알고리즘으로 짜더라도 구체적으로 어떤 전략을 가져가느냐에 따라 결과의 차이가 난다는 것이다.

코드: https://github.com/xgate/algospot/blob/master/DP/PI.cpp