[ Lv 2 ] 땅따먹기

풀이 과정

---

1. 행이 10만개나 가능하므로 탐색문제로 해결하면 시간초과

2. 따라서 dp를 활용하여 문제를 해결함.

3. i행 j열의 경우, 이전 행에서 j열을 제외한 나머지 열중 최댓값 + i행 j열의 값으로 대체

import copy
def solution(land):
    dp = copy.deepcopy(land)

    for i in range(1, len(land)):
        for j in range(len(land[0])):
            for k in range(len(land[0])):
                if k == j:
                    continue
                dp[i][j] = max(dp[i][j], dp[i-1][k] + land[i][j])

    return max(dp[len(land)-1])

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges