[백준알고리즘] 10164번: 격자상의 경로 -Python

[백준알고리즘] 10164번: 격자상의 경로 -Python

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

10164번: 격자상의 경로

경우의 수를 구해주는 문제이다. DP를 사용해 모든 경우의 수를 구해주면 된다.

 

O표시가 없는 경우(k=0인 경우)에는 시작점에서 끝점까지 이동할 수 있는 모든 경우의 수를 구해주면 된다.

(i, j)를 지날 수 있는 모든 경로의 수는 dp[i][j] = dp[i-1][j] + dp[i][j-1]의 간단한 점화식으로 구할 수 있다.

 

O표시가 있는 (i, j)에 있는 경우에는 (0, 0)에서 (i, j)까지의 경로의 수와 (i, j)에서 (n-1, m-1)까지의 경로의 수를 곱해주면 된다.

 

코드가 조금 지저분하다. 반복되는 부분이 세 번이나 들어가서 함수를 만드는 게 깔끔해 보이는데.. 수정하기 귀찮다..

n, m, k = map(int, input().split())
path = [[0]*m for _ in range(n)]
path[0] = [1]*m

if k == 0:
    for i in range(1, n):
        for j in range(m):
            path[i][j] = 1 if j == 0 else path[i-1][j] + path[i][j-1]
    print(path[-1][-1])
else:
    x, y = divmod(k-1, m)
    
    for i in range(1, x+1):
        for j in range(y+1):
            path[i][j] = 1 if j == 0 else path[i-1][j] + path[i][j-1]
    t = path[x][y]
    
    path[x] = [1]*m
    for i in range(x+1, n):
        for j in range(y, m):
            path[i][j] = 1 if j == y else path[i-1][j] + path[i][j-1]
    t *= path[-1][-1]
    print(t)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다