백준10164 - 격자상의 경로

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

10164번: 격자상의 경로

초등학교 때 풀었던 경우의 수 문제와 같았다. 이동하는 방향은 오른쪽, 아래 방향 두가지 방향으로 정해져있다. 격자 칸이 주어지고 각 격자칸으로 이동할 수 있는 모든 경우의 수를 이용하여 동적 계획법을 사용해서 구하였다. 

 

ex) 5 X 5칸이 주어진 경우 마지막 위치로 갈 수 있는 경우의 수

1	1	1	1	1
1	2	3	4	5
1	3	6	10	15
1	4	10	20	35
1	5	15	35	70

 

현재 이동할 수 있는 방법의 수는 현재 있는 칸의 바로 위의 칸과 바로 왼쪽 칸의 수를 더한 결과이다. 이 방법만 지키면 쉽게 풀 수 있다.

 

한가지 놓치면 안되는 점은 반드시 지나야 하는 점이 있기 때문에 DP를 두 번 진행해야 한다.

#include <iostream>
using namespace std;

int mat[15][15];
int ans[15][15];
int n, m, x;
int ex, ey;
int cnt = 1;

int main() {
	
	cin >> n >> m >> x;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (cnt == x) { //찾는 수의 행과 열의 값을 얻는다.
				ex = i;
				ey = j;
			}
			mat[i][j] = cnt;
			cnt++;
		}
	}

	//0번째 행의 값을 1로 초기화
	for (int i = 0; i < n; i++) {
		ans[i][0] = 1;
	}

	//0번째 열의 값을 1로 초기화
	for (int i = 0; i < m; i++) {
		ans[0][i] = 1;
	}
	
	//왼쪽 위의 부분의 DP값을 구한다. 1번째 행과 1번째 열부터 DP값 구하는 과정을 시행한다.(첫 줄은 1로 세팅했으니까)
	for (int i = 1; i <= ex; i++) {
		for (int j = 1; j <= ey; j++) {
			ans[i][j] = ans[i][j - 1] + ans[i - 1][j];
		}
	}

	//ex번째 행의 값을 왼쪽 위의 부분 마지막 DP값으로 초기화
	for (int i = ex; i < n; i++) {
		ans[i][ey] = ans[ex][ey];
	}

	//ey번째 열의 값을 왼쪽 위의 부분 마지막 DP값으로 초기화
	for (int i = ey; i < m; i++) {
		ans[ex][i] = ans[ex][ey];
	}

	//ex + 1번째 행과 ey + 1번째 행부터 DP값을 구한다.(오른쪽 아래 부분 DP를 구하는 과정)
	for (int i = ex + 1; i < n; i++) {
		for (int j = ey + 1; j < m; j++) {
			ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
		}
	}

	//최종 DP값 출력
	cout << ans[n - 1][m - 1];
}