[Flipkart 인터뷰] 금광

  n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 촐력하는 프로그램을 작성하세요.

입력 조건

- 첫째 줄에 테스트 케이스 T가 입력됩니다. (T는 1 이상 1000 이하)
- 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (n, m은 1 이상 20 이하), 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (각 위치에 매장된 금의 개수는 0 이상 100 이하)

출력 조건
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.

 

입력 예시

2
3 4 
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 6 1 2

출력 예시

19
16

---

  초반에 각 컬럼에 대해서 최대값을 구하는 함수를 구현해서 간단하게 구현해보려고 했습니다만, 그리디한 유형의 문제는 아니기 때문에 전체 경우에 대한 고려가 필요했습니다. 따라서 금광의 크기와 같은 크기의 DP table을 작성하여 모든 좌표의 경우의 수에 대해서 캐싱하도록 했습니다. 소스 코드는 다음과 같습니다.

T = int(input())
for _ in range(T):
    n, m = list(map(int, input().split()))
    array = []
    string = input().split()
    for i in range(0, len(string), m):
        array.append(list(map(int, string[i:i + m])))
    

    array = [[-1] * m] + list(map(lambda x: [-1] + x, array)) + [[-1] * m]
    table = [[-1] * (m + 1) for _ in range(n + 2)]
    
    print(array)
    print(table)

    for i in range(1, n + 1):
        table[i][1] = array[i][1]

    for i in range(2, m + 1):
        for j in range(1, n + 1):
            table[j][i] = max(table[j - 1][i - 1], table[j][i - 1], table[j + 1][i - 1]) + array[j][i]

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

    print(result)

 

 핵심이 되는 것은 array와 table에 대해서 -1로 패딩해준다는 점입니다. 이는 두가지 측면에서 이점을 가집니다. 첫번째, 좌표에 대해서 직관적으로 접근할 수 있습니다. 두번째, 예외처리를 대신합니다. 금의 개수는 언제나 0 이상이기 때문에 다른 좌표의 금의 양과 혼동될 일도 없으며, -1이 더해지는 경우의 수는 최대값이 될 수 없으므로 항상 제외됩니다.

[[-1, -1, -1, -1],
 [-1, 1, 3, 1, 5],
 [-1, 2, 2, 4, 1],
 [-1, 5, 0, 2, 3],
 [-1, 0, 6, 1, 2],
 [-1, -1, -1, -1]]

 

 DP table의 첫 번째 열의 원소는 금광의 첫 번째 열의 원소와 동일합니다. 이 초기화를 바탕으로 다음과 같은 점화식을 작성하면 최종적으로 table은 다음과 같이 초기화됩니다.

[[-1, -1, -1, -1, -1],
 [-1, 1, 5, 8, 16],
 [-1, 2, 7, 11, 14],
 [-1, 5, 5, 13, 16],
 [-1, 0, 11, 12, 15],
 [-1, -1, -1, -1, -1]]

 따라서 table의 마지막 열에 대해서 최대값을 찾으면 정답이 됩니다.