[프로그래머스] 땅따먹기

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12913

문제 설명

• N * 4 배열이 주어짐
• 한 행씩 내려옴
• 4칸 중 한 칸만 밟을 수 있음
• 이전 열이랑 같은 열 못 밟음
• 밟은 칸 합의 최댓값

풀이

• [이전 행에서 가능한 열들 중 최댓값] + [현재 행, 열의 값]

코드

def solution(land):

    dp = [[0]*4 for _ in range(len(land))]
    dp[0] = land[0]
    
    for i in range(1, len(land)):       # 10만
        for j in range(4):              # 4
            maxValue = float("-inf")
            for k in range(4):          # 4
                if j == k:
                    continue
                maxValue = max(maxValue, dp[i-1][k])
            dp[i][j] = maxValue + land[i][j]
                
    return max(dp[-1])