[문제해결을 위한 창의적 알고리즘] 격자길 (고급, p163)

이 문제는 0,0부터 n,m까지 갈 수 있는 길의 방법을 구하는 문제이다. 이전 포스트의 광석 수집 문제와도 비슷해 보인다. 한가지 신경쓸 점은 0,0부터 n,m까지 잇는 선보다 위쪽에 있는 점은 거쳐갈 수 없다는 점이다. 다이내믹 테이블이 채워지는 과정을 보면 더 이해가 쉬울 것같다.

import java.util.Scanner;

public class Crossway163 {

public static int n, m;

public static int[][] dt = new int[101][101];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

m = sc.nextInt();

sc.close();

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

for (int j = 0; j <= m; j++){

if (i ==0 && j==0)

dt[i][j]=1;

else{

// 왼쪽에서 오는 방법 수 더하기

if (i*m >= j*n && j >0)

dt[i][j]+=dt[i][j-1];

// 위쪽에서 오는 방법 수 더하기

if ((i-1)*m >= j*n && i>0)

dt[i][j]+=dt[i-1][j];

}

}

System.out.println(dt[n][m]);

/*

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

for (int j =0; j <=m; j++){

System.out.print(dt[i][j]+" ");

}

System.out.println("");

}

*/

return;

}

}

다이내믹 테이블 값 (n:3, m:4):

1 0 0 0 0 

1 1 0 0 0 

1 2 2 0 0 

1 3 5 5 5 

Big O(n*m)

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

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