[문제해결을 위한 창의적 알고리즘] 돌다리 건너기 (고급, p178)

이 문제는 중급편에서도 나왔던 문제인데, 동적계획법 (Dynamic Programming)으로 풀려고 하면 다이내믹 테이블을 생각해 내기 쉽지 않은 문제로 보인다. 다이내믹 테이블이 어떻게 만들어지는지 보면서 풀어보면 좋을 것 같다. 아래에서 'DT[s][r]=s돌다리에서 r번 문자로 끝나는 모든 경우'이다.

import java.util.Scanner;
	public class StoneBridgeSol183 {
	public static char[] rol = new char[30];
	public static char[][] dol = new char[2][120];
	public static int[][] DT = new int[2][30];
	public static int rc;
	public static int f(int k){
	// 돌다리 길이로 반복
	for(int i = 0; i <dol[1].length;i++){ // 두루마리 길이로 거꾸로 반복하면서 돌다리와 두루마리 글자가 같으면 방법 수 더함
	for (int t=k-1; t>=0; t--) {
	if (dol[0][i]==rol[t])
	DT[1][t+1]+=DT[0][t];
	if (dol[1][i]==rol[t])
	DT[0][t+1]+=DT[1][t];
	}
/*	for (int l = 0; l<2; l++){
	for (int m = 0; m<=rc; m++)
	System.out.print(DT[l][m]+" ");
	System.out.println("");
	}
	System.out.println("");
*/
	}
	return DT[0][k]+DT[1][k];
	}
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	rol = sc.next().toCharArray();
	dol[0]=sc.next().toCharArray();
	dol[1]=sc.next().toCharArray();
	sc.close();
	rc = rol.length;
	DT[0][0]=1;
	DT[1][0]=1;
	System.out.println(f(rc));
	return;
	}
	}

Big O(n*m): n: 두루말이 길이,  m: 돌다리 길이

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/StoneBridgeSol183.java 

문제해결을 위한 창의적 알고리즘 목록

출처: 한국정보올림피아드 (2004 전국본선 고등부)