[BOJ 10164] 격자상의 경로

문제

격자상의 경로

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

 

 

풀이

설명

조건을 만족하는 서로 다른 경로의 수를 구하는 문제입니다.

 

조건은 다음과 같습니다.

1. 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있습니다. (즉, 대각선 방향으로는 이동할 수 없습니다.)
2. 격자에 O로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 합니다.
   1. 1번 칸과 N × M번 칸은 O 표시가 되어 있지 않습니다.
   2. O 표시가 되어 있는 칸은 최대 한 개입니다.

 

DP를 사용해 해결할 수 있습니다.

 

O 표시가 된 칸을 K라고 할 때, 격자에서 갈 수 있는 영역은 K의 우상단과 K의 좌하단입니다.

따라서 해당 부분에 대한 경로만 구하면 됩니다.

 

예시 코드

function solution() {
  const [N, M, K] = input().split(" ").map(Number);
  const kx = Math.ceil(K / M),
    ky = ((K - 1) % M) + 1;
  const dp = Array.from({ length: N + 1 }, () => Array(M + 1).fill(0));
  dp[1][0] = 1;

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      // K 우상단
      if (i < kx && j > ky) continue;
      //K 좌하단
      if (i > kx && j < ky) continue;
      dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
    }
  }

  return dp[N][M];
}