프로그래머스|땅따먹기

문제 설명

행렬을 입력받고 한 행마다 숫자 하나를 선택해서 더한 값 중 최댓값을 구하는 문제입니다. 단 숫자를 선택할 때 같은 열의 숫자는 연속으로 선택할 수 없습니다.

작동 순서

1. 행렬을 입력받습니다.
2. 현재 위치 값+이전 행에서 본인과 같은 열을 제외한 값 중 가장 큰 값이 이번 행까지 내려오면서 만들 수 있는 가장 큰 값입니다.
3. 모든 행을 다 계산한 후 마지막 행에서 가장 큰 열의 값을 출력합니다.

소스코드

def solution(land):
    length=len(land)
    dp=[[0, 0, 0, 0] for _ in range(length)]
    for i in range(4):
        dp[0][i]=land[0][i]
    for i in range(1,length):
        for j in range(4):
            maxNum=0
            for k in range(4):
                if j==k:
                    continue
                maxNum=max(maxNum, dp[i-1][k])
            dp[i][j]=maxNum+land[i][j]
    return max(dp[length-1])