[문제해결을 위한 창의적 알고리즘] 격자길 (고급, 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