경우의 수1 BOJ 10164 격자상의 경로 www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net DP를 연습하던 중에 재미있는 풀이로 풀 수 있어서 가져와 봤다. k가 존재하면 (0, 0)에서 k가 존재하는 인덱스 (i, j)까지 의 길 찾기 경우의 수 \(nCk\)로 구하고 그 k에서 (n - 1, m - 1)까지의 경우의수를 또 구하면 된다. 나이브하게 풀면 오버플로가 나고 dp테이블에 조합을 저장해 두고 풀어야 한다. 1 2 3 4 5 6 7 8 9 10 11 1.. 2020. 12. 3. 이전 1 다음