땅따먹기

 

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

프로그래머스

문제풀이

지문 설명과 테스트 케이스 예시가 좀 부족한 문제이다. 해당문제는 최고점을 구해야 하는 문제이며 이전 행의 결과가 다음 행의 결과로 이어지기에 점화식을 이용 DP를 사용할 수 있다.

 

• 같은 열을 제외한 이전 행의 최대 값을 구한다.
• 최대 값을 현재 행렬에 더한다.
• 마지막 인덱스에서 최대 값을 구하게 된다면 그게 최고점이 된다.

def solution(land):
    n, m = len(land), len(land[0])

    for i in range(1, n):
        for j in range(m):
            land[i][j] += max(land[i - 1][:j] + land[i - 1][j + 1 :])

    return max(land[-1])