격자상의 경로

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. k === 0 인 경우와 k !== 0 인 경우에 따라서 경로의 개수 출력

문제 풀이 step 1

  • 행의 수가 N 이고, 열의 수가 M 인 격자에서 시작점 1 x 1 에서 N x M 까지 이동하는 모든 경로를 구하는 문제입니다.
  • 이에 더불어 격자에는 중간 경로가 존재할 수 있고, 존재하지 않을 수도 있습니다.
  • 중간 경로가 존재한다면, 1 x 1 에서 N x M 까지 이동하는 모든 경로 중에서 중간 경로를 경유하는 경로의 개수를 출력해야 합니다.
  • 중간 경로가 존재하지 않는다면, 1 x 1 에서 N x M 까지 이동하는 모든 경로의 개수만 출력하면 됩니다.

문제 풀이 step 2

  • dp[n][m] = n 행 m 열까지 이동하는 서로 다른 경로의 개수
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 점화식은 “dp[n][m] = dp[n - 1] + dp[m - 1]” 입니다.
  • base 값은 격자의 1 행의 모든 원소에 1 값을, 1 열의 모든 원소에 1 값을 넣어주면 됩니다.
  • 우선, 점화식과 base 값을 이용해서 격자를 다 채웁니다.
  • 중간 경로가 없는 경우, 즉 k === 0 인 경우
    • 이 때는 그냥 dp [n][m] 을 출력하면 됩니다.
  • 중간 경로가 있는 경우, 즉 k !== 0 인 경우
    • 이 때는 우선 중간 경로의 좌표값을 구합니다. 예를 들어, 좌표값이 i, j 라고 가정하겠습니다.
    • 우선, 1 x 1 부터 i x j 까지의 경로의 개수를 구합니다. 이는 dp[i][j] 입니다.
    • 그리고 i x j 부터 n x m 까지의 경로의 개수를 구합니다. 이는 dp[n + 1 - i][m + 1 - j] 입니다. 두 좌표를 서로 뺀 것입니다.
    • 이 둘을 곱하면 중간 경로를 경유하는 모든 경로의 개수가 나옵니다.
    • dp[i][j] x dp[n + 1 - i][m + 1 - j]
  • 각 경우에 따라서 경로의 개수를 구하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 중학생 시절의 수학 문제가 생각나는 문제였습니다.

소스 코드 1

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [n, m, k] = input[0].split(" ").map(Number);

	const dp = Array.from({length: n + 1}, () => Array(m + 1).fill(0));
	// base 값 채우기
	for (let i = 1; i < n + 1; i++) dp[i][1] = 1;
	for (let j = 1; j < m + 1; j++) dp[1][j] = 1;

	// 점화식과 base 값을 이용해서 dp 배열 채우기
	for (let i = 2; i < n + 1; i++) {
		for (let j = 2; j < m + 1; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}

	// 중간 경로가 없는 경우
	if (k === 0) return dp[n][m];

	let cnt = 0;
	let [midX, midY] = [0, 0];
	// 중간 경로의 좌표 구하기
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			cnt++;
			if (cnt === k) [midX, midY] = [i + 1, j + 1];
		}
	}

	// 중간 경로의 좌표를 경유하는 이동 경로의 개수 출력
	return dp[midX][midY] * dp[n + 1 - midX][m + 1 - midY];
};

console.log(solution(input));