문제
N×M 격자에서 (1,1)에서 (N,M)까지 오른쪽 또는 아래로만 이동한다. 특정 칸 K를 반드시 지나야 할 때(K=0이면 제약 없음), 가능한 경로 수를 구하라.
입력
한 줄에 N, M, K가 주어진다 (K는 칸 번호, 0이면 제약 없음).
출력
경로의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 4 0 | 10 |
풀이
격자 경로 DP를 구한 뒤, 중간점이 있으면 곱의 법칙을 적용한다.
p[i][j]를 (0,0)에서 (i,j)까지의 경로 수로 DP를 채운다- 첫 행/열은 1로, 나머지는
p[i][j] = p[i-1][j] + p[i][j-1]이다 - K가 0이면
p[N-1][M-1]을 출력한다 - K가 있으면 칸 번호를 (x, y) 좌표로 변환하고,
p[x][y] * p[N-1-x][M-1-y]를 출력한다 (출발→K 경로 수 × K→도착 경로 수)
핵심 아이디어: 중간 경유점이 있으면 (출발→경유) 경로 수와 (경유→도착) 경로 수를 곱하면 된다. 격자 경로 수는 조합으로도 구할 수 있지만 DP가 범용적이다.
코드
package day399;
import java.io.*;
import java.util.*;
public class Day377BOJ10164격자상의경로 {
static int N, M, K;
static int[][] p;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
p = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i == 0 || j == 0)
p[i][j] = 1;
else
p[i][j] = p[i - 1][j] + p[i][j - 1];
}
}
if (K != 0) {
int x = (K - 1) / M;
int y = (K - 1) % M;
System.out.println(p[x][y] * p[N - x - 1][M - y - 1]);
} else {
System.out.println(p[N - 1][M - 1]);
}
}
}복잡도
- 시간: O(N * M)
- 공간: O(N * M)