BOJ (C/C++) 10164번: 격자상의 경로

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

10164번: 격자상의 경로

---

풀이

(0,0) ~ (15,15)까지의 배열을 구한 후, K 값에 따라 적절한 값을 찾아 서로 곱해주었다.

예제 입력 1

예제 1의 경우 노란색의 (0,0) ~ (1,2) , 초록색의 (1,2) ~ (2,4)까지의 배열 값을 곱해주면 K=8을 지나는 총 경로의 갯수이다.

이 때 초록색의 (1,2) ~ (2,4)는 (0,0) ~ (1,2) 즉, (0,0) ~ (N-k_x-1, M-k_y-1) 값과 같다.

---

코드

#include <stdio.h>
int main() {
	int N, M, K;
	int DP[16][16];
	int kx, ky, r1, r2;
	scanf("%d %d %d", &N, &M, &K);

	for (int i = 0; i < 16; i++) DP[0][i] = DP[i][0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			DP[i][j] = DP[i - 1][j] + DP[i][j - 1];
		}
	}

	// K값에 따른 격자 상의 위치
	if (!K) kx = N - 1, ky = M - 1;
	else if (K%M == 0) kx = K / M - 1, ky = M - 1;
	else kx = K / M, ky = (K%M) - 1;

	printf("%d", DP[kx][ky] * DP[N - kx - 1][M - ky - 1]);
	return 0;
}