금광 (DP)

19 Feb 2021 in ALGORITHM

‘풀이시간 30분 , 시간제한 1초, 메모리제한 128MB, Flipkart 인터뷰 (취코테 375p)’

처음 이 문제를 해결할 땐 매 열의 최댓값을 구하고 해당 최댓값의 인덱스 값을 dp로 저장하여 해당 인덱스의 우측 상단, 우측, 우측하단의 인덱스를 구하여 최댓값을 갱신하는 방법으로 해결 하였다. 하지만 이것보다 더 간결한 방법이 있다.

첫번째 왼쪽열은 어디서든 출발해도 상관없으므로 값을 그대로 두고, 두번째열부터 왼쪽 상단의 값과 왼쪽의 값, 왼쪽 하단의 값과 자신을 더한 값이 최대인 값을 입력받는다.
이를 점화식으로 나타내면 다음과 같다.

  dp[i][j] = arr[i][j] + max(dp[i - 1][j - 1], dp[i][j - 1], dp[i + 1][j - 1])

그런데 여기서 중요한건 인덱스의 범위를 벗어나지 않는가이다. 벗어나는 경우는 2가지 경우 뿐이다. 좌측상단인 i == 0 인 경우와 가장 좌측 하단인 i == n - 1인 경우이다. 이 경우는 그냥 범위를 벗어난 값을 0으로 저장하면 최댓값 갱신될때 자연스럽게 무시되고 갱신된다.
이 방법으로 끝까지 dp를 갱신한 후엔 dp의 마지막 열에서 최댓값을 찾아내면 그 값이 원하는 값이다.

# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
    # 금광 정보 입력
    n, m = map(int, input().split())
    array = list(map(int, input().split()))

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index + m])
        index += m

    # 다이나믹 프로그래밍 진행
    for j in range(1, m):
        for i in range(n):
            # 왼쪽 위에서 오는 경우
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            # 왼쪽 아래에서 오는 경우
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            # 왼쪽에서 오는 경우
            left = dp[i][j - 1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)

    result = 0
    for i in range(n):
        result = max(result, dp[i][m - 1])

    print(result)