[Python] 12785 토쟁이의 등굣길 - Gold 3

w, h = map(int, input().split())

x, y = map(int, input().split())
mod = 1_000_007
x -= 1
y -= 1
dp = [[0] * w for _ in range(h)]

dp[0][0] = 1
for i in range(y + 1):
    for j in range(x + 1):
        if i > 0:
            dp[i][j] += dp[i - 1][j]
        if j > 0:
            dp[i][j] += dp[i][j - 1]

for i in range(y, h):
    for j in range(x, w):
        if i > y:
            dp[i][j] += dp[i - 1][j]
        if j > x:
            dp[i][j] += dp[i][j - 1]

print(dp[-1][-1] % mod)

조합에 관한 문제

학교 다닐때 풀었던 조합 문제를 프로그래밍 해서 푸는문제

문제는 2가지 파트로 나뉜다

집 -> 토스트 까지의 경우의 수
토스트 -> 학교 까지의 경우의 수

점화식은 dp[y][x] = dp[y-1][x] + dp[y][x-1]

시간 복잡도는 루프를 두번 돌아서 O(N^2)이다!

먼저 집 -> 토스트 가게 까지 위의 점화식으로 루프를 돌면서 구하고
다시 토스트 가게 부터 -> 학교까지의 경우의수를 똑같은 방법으로 구하면 된다.

solved는 난이도 골드 3인데 왜 골드 3인지 모르겠다;;