DP 정복 - 5.2 직사각형에서 총 경로 수 구하기

이번 예제는 BOJ에 비슷한 문제가 있다.

(https://www.acmicpc.net/problem/14904)

 

M * N의 방으로 구성된 직사각형이 있을 때

(0, 0)에서 (M, N)으로 이동하는 모든 경로의 수를 구하는 문제다.

단, 오른쪽 방향이나 아래쪽 방향으로만 이동이 가능하다.

(BOJ의 문제는 각 경로당 값 들이 존재해서 최댓값을 구해야 함)

 

일단 재귀 호출로 구현하면

1. 종료 조건 : 0, 0이면 0을 반환

2. 첫 번째 행이나 첫 번째 열이면 : 1을 반환

3. 오른쪽이나 왼쪽으로 이동하도록 재귀 호출

위의 내용을 구현하면 아래와 같다.

import sys

sys.setrecursionlimit(10 ** 5)


def solve(m, n):
    if m == 0 and n == 0:
        return 0
    if m == 0 or n == 0:
        return 1

    return solve(m - 1, n) + solve(m, n - 1)


if __name__ == '__main__':
    m, n = map(int, input().split())
    print(solve(m-1, n-1))

DP로 구현하기 위해서는

일단 0, 0은 0으로 내버려 두고,

(x, 0)과 (0, y)를 모두 1로 채운 뒤,

현재 위치에서 위와 아래의 값을 더해서 m, n까지 구해주면 된다.

위의 내용을 구현하면 아래와 같다.

def solve_dp(y, x):
    cache = [[0 for _ in range(x)] for __ in range(y)]
    for i in range(1, x):
        cache[0][i] = 1
    for i in range(1, y):
        cache[i][0] = 1

    for i in range(1, y):
        for j in range(1, x):
            cache[i][j] = cache[i - 1][j] + cache[i][j - 1]

    return cache[y - 1][x - 1]


if __name__ == '__main__':
    y, x = map(int, input().split())
    print(solve_dp(y, x))

예전에 분명히 풀어봤던 문제였는데

머릿속이 새하얗..... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

역시 계속 반복하는 게 가장 좋음.