[BOJ] 10164 : 격자상의 경로 - travelbeeee

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

---

[ 알고리즘풀이 ]

 우리가 학창 시절에 배웠던 모든 경로의 수 세는 방법을 이용해 먼저 dp 배열을 다음과 같이 채웠습니다.

 dp[x][y] : 가로 x 줄, 세로 y칸 일 때 모든 경로의 수 로 정의하면,

 dp[1][y] = 1, dp[x][1] = 1, dp[x][y] = dp[x - 1][y] + dp[x][y - 1] 이 성립합니다.

1	1	1	1	1	1	1
1	2	3	4	5	6	7
1	3	6	10	15	21	28
1	4	10	20	35	56	84

 그 후, K에 맞춰 dp 배열을 참조해 모든 경로의 수를 구해주면 됩니다.

#include<iostream>

using namespace std;

int dp[16][16] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	for (int i = 1; i <= 15; i++)
		dp[i][1] = 1, dp[1][i] = 1;
	for (int i = 2; i <= 15; i++)
		for (int j = 2; j <= 15; j++)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

	int N, M, K, r, c;
	cin >> N >> M >> K;
	if (K == 0)
		cout << dp[N][M];
	else {
		r = ((K - 1) / M) + 1;
		c = ((K - 1) % M) + 1;
		cout << dp[r][c] * dp[N - r + 1][M - c + 1];
	}
}

---