[알고리즘] 땅따먹기

문제

행이 M, 열이 4인 땅이 있을 때 첫번째 행에서 마지막 행까지 내려가고자 한다. 단, 해당 위치에서 같은 열의 위치로 내려갈 수 없다. 예를 들어, 땅 따먹기 판이 아래와 같다.

5 3 4 2
1 7 2 5
1 2 3 1
3 3 2 3

만약에 첫번째 행의 4번째인 2에 위치해있을때, 아래로 내려갈 때 같은 행인 5로 내려갈 수 없다. 이때, 첫번째 행에서 마지막행까지 내려갈 때 거치는 자리의 값들의 합에서 나올수 있는 최대값을 구하자.

입력

[ [5,3,4,2], [1,7,2,5], [1,2,3,1], [3,3,2,3]]

출력

18

풀이

• KEY : i,j의 위치의 원소까지 탐색했을 때, 이전 행들을 거쳐서 올 수있는 최대값들을 저장해놓자.
• 예를 들어,
  • 2번째 행의 1번째 열에 올수 있는 최대값은, 1번째 행의 3번째 열의 값인 4 에 자신의 값 1 을 더한 5 이다.
  • 2번째 행의 2번째 열에 올수 있는 최대값은, 1번째 행의 1번째 열의 값인 5 에 자신의 값 7 을 더한 12 이다.
  • 3번째 행의 2번째 열에 올수 있는 최대값은, 2번째 행의 4번째 열의 최대 값인 10 에 자신의 값 2 을 더한 12 이다.
  • 계속해서 값을 채워나가면 마지막 행의 최대 값들까지 채울 수 있다.
  • 마지막 행중에 가장 큰 값이 누적한 최대 값을 의미한다.
• mat[i][j] = max(mat[i-1][0] ... mat[i-1][k] ... mat[i-1][3] (k != j)) + board[i][j]

# 2 번째행 최대 값 누적
[ 5,  3,  4,  2]
[ 5, 12,  7, 10]
[ 0,  0,  0,  0]
[ 0,  0,  0,  0]
# 3번째 행 최대 값 누적
[ 5,  3,  4,  2]
[ 5, 12,  7, 10]
[13, 12, 15, 13]
[ 0,  0,  0,  0]
# 4번째 행 최대값 누적
[ 5,  3,  4,  2]
[ 5, 12,  7, 10]
[13, 12, 15, 13]
[18, 18, 15, 18]

작성 코드

def solution(land):
    answer = 0
    ans_list = []
    N = len(land)
    # 누적 최대 값 저장할 이중 배열 ans_list 초기화
    for i in range(N):
        r = []
        for j in range(4):
            if (i == 0):
                r.append(land[i][j])
            else:
                r.append(0)
        ans_list.append(r)

    # 누적 최대 값 저장
    for i in range(1,N):
        for j in range(4):
            mx = 0
            for k in range(4):
                if( j != k):
                    if( ans_list[i-1][k] + land[i][j]  > mx):
                        mx = ans_list[i-1][k] + land[i][j] 
            ans_list[i][j] = mx
    # ans_list의 마지막행에서의 최대 값 찾아내기
    mx = 0
    for i in range(4):
        if(mx < ans_list[N-1][i]):
            mx = ans_list[N-1][i]

    return mx


print(solution([ [5,3,4,2], [1,7,2,5], [1,2,3,1], [3,3,2,3]]))