[백준]10164. 격자상의 경로(python, 파이썬)

문제

10164. 격자상의 경로

📌 아이디어

이 문제는 DP를 활용하여 주어진 조건에 해당되는 모든 경우의 경로를 탐색할 수 있었습니다.

1. 크게 위치 K 도달 전, 후 2가지로 나누어 탐색을 진행합니다.
2. 탐색을 진행한다면 첫 위치는 1로 고정하고, 그 외의 경우는 아래를 이동한 dp[i-1][j]와 오른쪽을 이동한 dp[i][j-1] 두 가지 경우를 합해갑니다.
3. 만약 K가 0인 경우는 두 가지 경우로 나누지 않고 행과 열을 N, M으로 하여 모든 경우를 탐색합니다.

📌 코드

N, M, K = map(int, input().split())

def search(n, m):
    dp = [[0] * (m+1)] * (n+1)

    for i in range(1, n+1):
        for j in range(1, m+1):
            # 첫 위치의 경우는 1
            if i == 1 and j == 1:
                dp[i][j] = 1
            # 아래와 오른쪽으로 이동하는 두 가지 경우를 합하기
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[n][m]

if K:
    # n1, m1은 K까지 이동할 수 있는 모든 경로를 탐색
    n1 = (K-1)//M + 1
    m1 = K - (n1 - 1) * M
    # n2, m2은 K에서 마지막까지 이동할 수 있는 모든 경로를 탐색
    n2 = N - (n1 - 1)
    m2 = M - (m1 - 1)
    rst1 = search(n1, m1)
    rst2 = search(n2, m2)
    # 모든 경우의
    print(rst1 * rst2)
# K가 0인 경우는 N부터 M까지의 모든 경로를 탐색
else:
    print(search(N, M))

피드백 및 개선점은 댓글을 통해 알려주세요😊