[문제해결을 위한 창의적 알고리즘] 공주 구하기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

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

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