2017 카카오코드 예선

보행자 천국

🔗 전체 문제 : 보행자 천국

다이나믹 프로그래밍

1. 왼쪽 -> 오른쪽
2. 위쪽 -> 아래쪽
   두가지 경우를 더하여 각 방향의 경우의 수를 구하는 문제

• 메모이제이션 : 이미 계산한 결과 배열에 저장

def solution(m,n,city_map):
    mod = 20170805
    goRight = [[0] * (n+1) for _ in range(m+1)]
    goDown = [[0] * (n+1) for _ in range(m+1)]
    goRight[1][1] = 1
    goDown[1][1] = 1
    
    for i in range(1,m+1):
        for j in range(1,n+1):
            if city_map[i-1][j-1] == 0:
                goRight[i][j] += (goRight[i-1][j] + goDown[i][j-1]) % mod
                goDown[i][j] += (goRight[i-1][j] + goDown[i][j-1]) % mod
            elif city_map[i-1][j-1] == 1:
                goRight[i][j] = 0
                goDown[i][j] = 0
            else:
                goRight[i][j] = goRight[i-1][j]
                goDown[i][j] = goDown[i][j-1]

    return (goRight[m-1][n] + goDown[m][n-1]) % mod

# test
print(solution(3,3,[[0, 0, 0], [0, 0, 0], [0, 0, 0]]))
print(solution(3,6,[[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]]))