금광 파이썬 풀이 - Dynamic programming

금광

이동방향은 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 이다.

이를 현재 내 위치인 dp[i][j]에서 보면 왼쪽 위, 왼쪽, 왼쪽아래에서 내 위치로 오는 3 가지 경우가 있다는 의미이다 

하지만 이렇게 i == 0 인 경우에는 왼쪽위에서 올 수 없으므로 left_top = 0 이다. 그렇지 않은 경우에는 left_top = dp[i-1][j-1] 이다.

다음의 경우는 3가지 방향 모두 유효하니까 경우를 더 나눌 필요 없이, left = dp[i][j-1]

i == (n-1) 인 경우에도 왼쪽아래에서 오는 경우는 불가능 하므로 이 경우 left_bottom = 0이라고 처리해 준다. 

그렇지 않은 경우는 left_bottom = dp[i+1][j-1] 이다.

그리고 이 값들 중에서 max 값과 dp[i][j]을 더한 값을 dp[i][j] 에 저장한다 ! 

# pg 375

t = int(input())
for _ in range(t):
    n,m = map(int, input())
    array = list(map(int, input()))

    # 2차원 DP 테이블을 초기화 하는 과정
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index+m])
        index += m

    # DP 진행
    for j in range(1, m):
        for i in range(n):
            # 왼쪽 위에서 오는 경우
            if i == 0:
                left_top = 0
            else:
                left_top = dp[i-1][j-1]
            # 왼쪽에서 오는 경우
            left = dp[i][j-1]
            # 왼쪽아래에서 오는 경우
            if i == n-1:
                left_bottom = 0
            else:
                left_botton = dp[i+1][j-1]
            dp[i][j] = dp[i][j] + max(left_top, left, left_botton)

    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1]) # 맨 마지막 줄 값 비교하기
    print(result)