[종만북]8.동적 계획법-원주율 외우기

문제

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

(주의: 이 문제는 TopCoder 의 번역 문제입니다.)

가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

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

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.

출력

각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.

풀이(나의 풀이)

먼저 어떤 부분을 메모이제이션을 통해 구현할 지 생각해 봤을 때, 입력받은 문자열에 대해 길이가 3 이상인 부분문자열을 분리하여 난이도를 계산하고, 계산된 답을 메모이제이션으로 저장하고자 하였다. 길이가 0인 경우, 기저사례로 0을 리턴하고 이외의 경우 난이도를 판별하고자 하였는데, 계산된 난이도를 비교하고 최솟값을 계산하는 부분을 생각해내기가 어려웠다. 또한, 단순히 문자열 전체에 대해 특정 문자열에 대한 메모이제이션을 저장하고자 하여(예를들어, 조각 12345의 답을 계산한 경우 cache[12345]에 저장) 메모이제이션을 구현하지 못하였다.

풀이(책 참고)

앞서 푼 JLIS문제와 마찬가지로, 문자열을 분해하는 동적 계획법 문제를 풀 때 입력받은 문자열에 대해 문자열 자체를 메모이제이션에 저장할 필요가 없이, 해당 문자열의 시작 인덱스, 또는 시작과 종료 인덱스를 메모이제이션을 통해 구현하면 되는 것이다. 문자열을 분해할 때마다 앞 또는 뒤의 문자열을 재귀적으로 호출하게 되므로, 이 때의 인덱스에 대한 답만 저장하여도 메모이제이션을 통해 이에 대한 풀이가 가능해진다.

따라서 이를 구현하면 다음과 같다.

// classify(a,b) = a부터 b 인덱스 까지의 부분문자열에 대한 난이도 판별
static int PI(int start) {
		if (start==s.length())
			return 0;
		
		int ret = cache[start];
		if (ret != -1)
			return ret;
		
		ret = cache[start] = 987654321;
		for(int i=3;i<=5;i++) {
			if(start+i<=s.length())
				ret = cache[start]= 
                Math.min(ret, PI(i+start)+classify(start, i+start-1));
		}
		return ret;

	}

시작 인덱스가 문자열의 길이가 같은 경우, 즉 문자열의 길이가 0인경우를 기저사례로 두고 초기 ret값을 매우 큰값으로 초기화하여, 입력받은 start인덱스를 기준으로 길이가 3부터 5까지의 부분문자열에 대한 난이도 값과 나머지 문자열의 PI 메소드(재귀적 호출)를 통한 값을 비교하여 최솟값을 계산하도록 구현한다.

Menu

문제

입력

출력

풀이(나의 풀이)

풀이(책 참고)