[Baekjoon 10164] 격자상의 경로 | Python

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

---

문제

 

오른쪽과 아래쪽으로밖에 이동하지 못하는 로봇이 제시된 공간에서 이동하는 경로의 경우의 수를 구하는 문제이다. 만약 동그라미가 표시된 공간이 있다면 반드시 지나야 한다.

 

---

풀이

 

고등학교 확률및통계에 나오는 최단거리 경우의 수를 활용하면 된다. 최단거리가 되는 이유는 로봇이 오른쪽과 아래쪽으로 밖에 못 움직이기 때문이다. 즉 로봇이 오른쪽으로 이동하거나 아래쪽으로 이동하는 두 개의 경우를 나열한 경우의 수를 확인하면 된다.

최단거리 문제에서 $ n \times m $ 에서의 경우의 수는 $ C(n+m, n) $, 즉 $ \dfrac{(n+m)!}{n! \times m!} $ 이다. 그런데 이 경우는 선에서 움직이는 경우이고, 문제는 격자에서 움직이는 경우이니 이동하려는 행과 열의 수에서 $ 1 $을 빼고 계산해야 한다.

동그라미 표시가 없는 경우를 가정할 때는 시작부터 끝까지 이동경로를 확인하면 된다. 즉 주어진 $ n $, $ m $ 에 대해 $ \dfrac{(n-1+m-1)!}{(n-1)! \times (m-1)!} $ 를 계산하면 된다.

그러나 동그라미 표시가 있다면 시작부터 동그라미까지 이동 가능한 경우의 수와 동그라미부터 끝까지 이동 가능한 경우의 수를 곱해주어야 한다. 즉 동그라미의 위치를 찾아야 한다. 동그라미는 수로 주어지는데 문제의 예시를 통해 확인할 수 있지만 행의 위치는 $ (k - 1) / m + 1 $ 이고, 열의 위치는 $ (k-1) \bmod m + 1 $ 이다.

이를 이용하여 동그라미까지의 경우의 수와 동그라미부터의 경우의 수를 구해준다면 총 서로 다른 경로의 경우의 수를 구할 수 있다.

 

---

코드

 

from math import comb

x, y, won = map(int, input().split())
if won == 0:
        print(comb(x+y-2, x-1))
else:
    won_x = (won - 1) // y + 1
    won_y = (won - 1) % y + 1
    print(comb(won_x+won_y-2, won_x-1) * comb(x+y-won_x-won_y, x-won_x))