[Baekjoon 10164] 격자상의 경로 | Python
·
Online Judge/Baekjoon
https://www.acmicpc.net/problem/10164문제 오른쪽과 아래쪽으로밖에 이동하지 못하는 로봇이 제시된 공간에서 이동하는 경로의 경우의 수를 구하는 문제이다. 만약 동그라미가 표시된 공간이 있다면 반드시 지나야 한다. 풀이 고등학교 확률및통계에 나오는 최단거리 경우의 수를 활용하면 된다. 최단거리가 되는 이유는 로봇이 오른쪽과 아래쪽으로 밖에 못 움직이기 때문이다. 즉 로봇이 오른쪽으로 이동하거나 아래쪽으로 이동하는 두 개의 경우를 나열한 경우의 수를 확인하면 된다.최단거리 문제에서 $ n \times m $ 에서의 경우의 수는 $ C(n+m, n) $, 즉 $ \dfrac{(n+m)!}{n! \times m!} $ 이다. 그런데 이 경우는 선에서 움직이는 경우이고, 문제는 격자에서..