[문제해결을 위한 창의적 알고리즘] 공주 구하기 (고급, p191)

이 문제도 중급에서 다뤘던 문제이지만, 여기서는 성능을 좀 더 개선해 볼 수 있는 방법으로 메모이제이션 기법을 이용한 풀이를 적어보고자 한다. 두명의 다리오가 있다고 하고 한명은 유시섬에서 후퍼섬으로 가고 한명은 후퍼섬에서 유시섬으로 오는 상황에서 

f(a, b, k) = "가는 다리오가 a 위치의 섬에 있고, 오는 다리오가 b 위치의 섬에 있으며, 다음으로 방문할 섬은 k위치의 섬에 대해서 탐색하려고 하는 상태"로 정의한다.

import java.util.Scanner;

public class SavePrincessSol195 {

public static final int MOD = 1000;

public static int n;

public static int[] D = new int[501];

public static int[] S = new int[501];

public static int[] A = new int[501];

public static int[][] DT = new int[501][501];

public static int f(int a, int b, int k){

if (DT[a][b]==-1){

if (k==n-1)

return ((D[a]+S[a]>=D[k]) && (D[b]+S[k]>=D[k]))?1:0;

DT[a][b]=f(a,b,k+1);

if(D[a]+S[a]>=D[k])

DT[a][b]+=f(k,b,k+1);

if (D[b]+S[k]>=D[k] && A[k]>0)

DT[a][b]+=f(a,k,k+1);

DT[a][b]%=MOD;

}

return DT[a][b];

}

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

for (int i =0; i < 501; i++)

for (int j = 0; j<501; j++)

DT[i][j]=-1;

for (int i =0; i<n; i++){

D[i]=sc.nextInt();

S[i]=sc.nextInt();

A[i]=sc.nextInt();

}

sc.close();

System.out.println(f(0,0,1));

return;

}

}

Big O(2^n): f가 호출될때 마다 다음 단계로 가는 2가지 방법이 k가 n-1이 될 때까지 진행된다.

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

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

출처: 한국정보올림피아드 (2008 지역본선 고등부)