[이코테] 금광

출처 - 이것이 취업을 위한 코딩테스트다 with 파이썬

금광

📌 문제

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

📋 코드

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    tmp = list(map(int, input().split()))

    gold = []
    idx = 0
    for _ in range(N):
        gold.append(tmp[idx:idx+M])
        idx += M

    for j in range(1, M):
        for i in range(N):
            if i == 0:
                gold[i][j] = max(gold[i][j-1] + gold[i][j], gold[i+1][j-1] + gold[i][j])
            elif i == N-1:
                gold[i][j] = max(gold[i-1][j-1] + gold[i][j], gold[i][j-1] + gold[i][j])
            else:
                gold[i][j] = max(gold[i-1][j-1] + gold[i][j], gold[i][j-1] + gold[i][j], gold[i+1][j-1] + gold[i][j])

    result = 0
    for g in gold:
        result = max(result, max(g))
    print(result)

💡 한마디

DP 테이블을 따로 만들어주지 않고 gold 리스트를 갱신해가며 풀었다.

맨 위 행은 왼쪽이나 왼쪽 아래에서 도달할 수 있고, 맨 아래 행은 왼쪽 위나 왼쪽에서 도달할 수 있다. 그 외에는 왼쪽 위, 왼쪽, 왼쪽 아래 3가지 위치에서 도달할 수 있기 때문에 각각의 경우에 대한 최댓값을 계속 갱신해나갔다.