[백준] 10164 격자상의 경로 Python

 

 

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

10164번: 격자상의 경로

1. 문제 

이 문제는 N, M, K의 값을 받아서 N * M개의 칸을 가진 격자를 만들고 왼쪽에서 오른쪽으로 위에서 아래로 넘버링을 한다. 

그 다음 K가 0일 때는 1번 칸에서 N * M번 칸까지 격자의 변을 통해서만 이동하는 경우의 수를 구하고 

K가 0이 아닐 때는 K번 칸을 무조건 지나도록 갈 때의 경우의 수를 구하는 것이다. 

 

자세한 문제는 위 링크 안에 있다. 

 

2. 풀이

이 문제를 보자마자 이산수학에서의 최단경로의 수 문제가 생각이 났다.

x, y축으로 M, N칸을 가야할 때

(M+N)!/(N! * M!)를 통해서 경우의 수를 구하는 것이다.

 

 

def factorial(N) :
    if N >= 2 :
        return N*factorial(N-1)
    else :
        return 1
 

그것을 이용하기 위해서 일단 위의 코드 같이 재귀함수를 이용해서 factorial 함수를 만들었다. 

 

 

N, M, K = input().split(" ")
N, M, K = int(N), int(M), int(K)
 
if K == 0 :
    print(round(factorial(N + M - 2) / (factorial(N-1) * factorial(M-1))))
else :
    if K%M > 0 :
        y = (K//M + 1)
    else :
        y = (K//M)
    x = K - ((y-1) * M)
    print(round((factorial(x+y-2) / (factorial(x-1) * factorial(y-1)))*(factorial(M - x + N - y) / (factorial(M - x) * factorial(N - y)))))

1~2에서 N, M, K를 입력 받고 정수의 형태로 저장했다. 

 

4~5에서 K가 0일 때 1번 칸에서 M*N번 칸까지 갈 때 x축으로 M-1칸 y축으로 N-1칸을 가야하기에

(M+N-1)!/((M-1)!*(N-1)!)을 출력하도록 했다. 

 

7~11에서 K번째 칸의 x, y 좌표를 얻었다. 

 

12에서 K번 칸의 좌표를 이용해서 계산한 값을 출력하도록 했다.