백준 10164번 - 격자상의 경로

https://www.acmicpc.net/problem/10164

10164번: 격자상의 경로

 

[풀이]

​

DP로 풀면 되는 문제인데, O표시를 한 부분을 기준으로 생각하면 된다.

​

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15

 

위의 배열에서 8번에 O 표시가 되어 있으므로 1번에서 8번까지 가는 경로의 수 ( A ) 와 8번에서 15번까지 가는 경로 ( B ) 를 구한 후 곱해주면 된다.

​

총 경로의 수 = A * B

 

 

[소스코드]

 

 

import java.util.Scanner;

public class Main {	//bj10164	격자상의 경로
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int k=sc.nextInt();
		int[][] arr=new int[n][m];
		int num=0;
		int indexI=n;
		int indexJ=m;
		arr[0][0]=1;
		if(k!=0) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					num++;
					if(num==k) {
						indexI=i;
						indexJ=j;
					}
				}
			}
			for(int i=0;i<=indexI;i++) {
				for(int j=0;j<=indexJ;j++) {
					if(i+1<=indexI) arr[i+1][j]+=arr[i][j];
					if(j+1<=indexJ) arr[i][j+1]+=arr[i][j];
				}
			}
			for(int i=indexI;i<n;i++) {
				for(int j=indexJ;j<m;j++) {
					if(i+1<n) arr[i+1][j]+=arr[i][j];
					if(j+1<m) arr[i][j+1]+=arr[i][j];
				}
			}
			System.out.println(arr[n-1][m-1]);
		}
		else {
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(i+1<n) arr[i+1][j]+=arr[i][j];
					if(j+1<m) arr[i][j+1]+=arr[i][j];
				}
			}
			System.out.println(arr[n-1][m-1]);
		}
	}
}