[알고리즘] 백준 - 출근 경로

백준 - 출근 경로

다른 사람 풀이

dp = [[[0, 0, 0, 0] for _ in range(101)] for _ in range(101)]
w, h = map(int, input().strip().split())
MOD = 100000
# 1) 아래 아래 - dp[i][j][0]
# 2) 오른쪽 아래 - dp[i][j][1]
# 3) 오른쪽 오른쪽 - dp[i][j][2]
# 4) 아래 오른쪽 - dp[i][j][3]

for i in range(1, h+1):
    dp[i][1][0] = 1

for j in range(1, w+1):
    dp[1][j][2] = 1

for i in range(2, h+1):
    for j in range(2, w+1):
        # 위에서 아래로 내려오는 것
        dp[i][j][0] = (dp[i-1][j][1] + dp[i-1][j][0]) % MOD
        dp[i][j][1] = dp[i-1][j][2]

        # 왼쪽에서 오른쪽으로 오는 것
        dp[i][j][2] = (dp[i][j-1][3] + dp[i][j-1][2]) % MOD
        dp[i][j][3] = dp[i][j-1][0]

print(sum(dp[i][j]) % MOD)

다른 사람들 풀이를 보고도 이해가 안가서 고민을 많이 했다. 이제는 이해 했다. 결국 DP는 풀고나면 비슷한 형태인 것 같다.