Programmers - 땅따먹기

문제 링크

처음에는 각각 0행의 0~3열에서 시작해서 Greedy하게 탐색하는 방법을 떠올리고 반례를 생각해보았다.

land가 [[1,2,3,4],[10,0,0,0],[100,0,0,0]] 일 때, (0,3) -> (1,1~3) -> (2,0) 순으로

고르는 것이 최대값을 얻을 수 있지만, greedy하게 해당 시점에서 얻을 수 있는 최대 값을 쫒아서 탐색한다면

(0,3) -> (1,0) -> (2,1~3) 으로 탐색하게 되어 최대 값을 얻을 수 없는 것을 확인하고 다른 방법을 생각했다.

DP로 풀었는데, 수식은 다음과 같다

d[i][j] = i행 j열에서 얻을 수 있는 최대 값.
d[i][j] = land[i][j] + max(d[i-1][x],d[i-1][y],d[i-1][z]) / x,y,z 는 0,1,2,3 중 j를 제외한 3가지 숫자

(i,0)을 밟는다고 할 때, (i,0)으로 올 수 있는 칸은 이전에 (i-1,1),(i-1,2),(i-1,3) 을 밟은 경우이다. 이때, (i,0) 에 왔을 때 어디서 왔는지는 신경쓰지 않고 올 수 있는 칸 3가지 중에서 지금까지 가장 많은 득점을 얻은 곳에서 (i,0)을 밟았다고 생각하면 위와 같은 식을 얻을 수 있다.

def solution(land):

    d = [[0 for _ in range(4)] for _ in range(len(land))]

    # d[i][j] = i행 j칸에서 얻을 수 있는 최대 값
    # d[i][j] = land[i][j] + max(d[i-1][x],d[i-1][y],d[i-1][z])
    #           (x,y,z 는 0,1,2,3 중 j를 제외한 3가지 숫자)

    def get_max_without_j(row, j):
        max_value = 0
        for x in range(4):
            if x == j:
                continue
            max_value = max(max_value, d[row][x])
        return max_value

    d[0] = land[0]
    for i in range(1, len(d)):
        for j in range(4):
            d[i][j] = land[i][j] + get_max_without_j(i-1, j)

    return max(d[len(d)-1])