[문제해결을 위한 창의적 알고리즘] 공주 구하기2 (고급, p191)
앞선 포스트에서 메모이제이션 방법을 이용하여 푸는 방법을 적어보았다. 그러나 역시 동적계획법을 사용해야 성능이 보장된다고 할 수 있으므로, 이번에는 동적계획법 (Dynamic Programming) 방법을 이용해 푸는 방법을 알아보고자 한다. 책에는 오타가 있음을 유의한다.
아래에서 DT[a][b]=가는 다리오가 a의 위치 섬에, 오는 다리오가 b의 위치 섬에 있을 수 있는 모든 경우의 수라고 정의한다.
import java.util.Scanner;
public class SavePrincessSol197 {
public static final int MOD = 1000;
public static int n;
// 풀이에서는 array size가 501로 선언되어 있으나 n이 3~20까지이므로 20이면 충분하다
// D는 거리, S는 스프링 세기, A는 돌아올 때 사용할 수 있는지 여부
public static int[] D = new int[20];
public static int[] S = new int[20];
public static int[] A = new int[20];
public static int[][] DT = new int[20][20];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
for (int i = 0; i < n; i++){
D[i]=sc.nextInt();
S[i]=sc.nextInt();
A[i]=sc.nextInt();
}
sc.close();
// 모든 가는 다리오와 오는 다리오의 위치에 대하여
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
// 둘다 0에 있을 수 있는 경우의 수는 1
if (i==0 && j==0)
DT[i][j]=1;
// i와 j가 다른 경우만 가정 (한번 밟은 곳은 다시 밟을 수 없으므로, 그러나 마지막 섬에 모두 있는 것은 가능)
else if (i!=j || i==n-1 && j==n-1){
// 가는 다리오가 멀리 있는 경우
if (i > j){
for (int k=0; k <i; k++)
if (D[k]+S[k]>=D[i])
DT[i][j]+=DT[k][j];
}
// 그렇지 않은 경우라면 올때 사용할 수 있는 스프링이 있는 섬에 대해서만
else if (A[j]>0){
for (int k =0; k < j; k++)
if (D[k]+S[j]>=D[j])
DT[i][j]+=DT[i][k];
}
}
DT[i][j]%=MOD;
}
}
System.out.println(DT[n-1][n-1]);
/* for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)
System.out.print(DT[i][j]+" ");
System.out.println("");
}
*/
return;
}
}
입력 예제에 대해 동적테이블은 아래와 같이 채워진다.
입력:
8
0 7 1
3 4 1
6 8 1
8 6 1
12 2 0
13 2 1
14 2 1
15 7 1
동적테이블:
1 1 2 3 0 0 0 3
1 0 1 1 0 0 0 1
2 1 0 1 0 0 0 1
2 1 0 0 0 0 0 0
4 2 0 1 0 0 0 1
8 4 0 2 0 0 0 2
16 8 0 4 0 0 0 4
24 12 0 6 0 0 0 6
Big O(n^2)
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/SavePrincessSol197.java