[Python/파이썬] 백준 10164번 격자상의 경로

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

코드

n, m, k = map(int, input().split())


def find_path(r, c):    # 세로 길이가 r, 가로 길이가 c인 격자에서 경로의 개수 구하기
    dp = [[0]*(c) for _ in range(r)]
    dp[0][0] = 1
    for i in range(r):
        for j in range(c):
            if i+1 < r:
                dp[i+1][j] += dp[i][j]
            if j+1 < c:
                dp[i][j+1] += dp[i][j]
    return dp[r-1][c-1]


if k == 0:
    print(find_path(n, m))
else:
    r = (k-1)//m
    c = (k-1) % m
    # k에 도달할 때까지의 경우의 수
    prev = find_path(r+1, c+1)
    # k부터 N X M까지의 경우의 수
    next = find_path(n-r, m-c)
    print(prev*next)

 

풀이

목적지까지 경로의 개수 구하는데 중간에 꼭 경유해야 하는 곳이 있다면 다음과 같이 출발지-경유지까지 가는 길과 경유지-목적지까지 가는 길의 경로의 수를 각각 구해서 곱하면 된다.

1번이 출발지, 15번이 목적지, 8번이 경유지라면 (1번에서 8번까지 가는 경우의 수) × (8번에서 15번까지 가는 경우의 수)를 구하면 문제에서 요구하는 답을 구할 수 있다.

 

그렇기 때문에 직사각형이 있을 때 왼쪽 위에서 오른쪽 아래까지 가는 경우의 수를 리턴하는 함수 `find_path()`를 구현했다. find_path()는 각 칸까지 가는 경로의 수를 저장하는 dp 배열을 이용하여 오른쪽 아래까지의 경로를 구한다.

 

이제 주어진 N×M 사각형에서 경유지를 가장 오른쪽 아래 칸으로 포함하는 직사각형과 경유지가 가장 왼쪽 위에 오는 직사각형 하나로 나누어서 find_path() 함수를 적용하면 문제를 해결할 수 있다.