[프로그래머스/파이썬] Level 2 땅따먹기

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

---

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

처음 생각은 '각 행에서 내려올 때마다 최대값을 구해서 더해가면 되나?'였다.

그러나 그럴 경우 1|2|3|4,5|6|7|10이런 식이라면 5+7<3+10이 된다.

그러다 DP알고리즘을 떠올렸다. 1행 1열부터 위 행의 3개 열과 더해서 최대값으로 갱신해가는 것이다.

예시)
[[1, 2, 3, 5], [7, 6, 7, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [8, 6, 7, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 6, 7, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 7, 7, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 9, 7, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 11, 7, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 11, 8, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 11, 9, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 11, 12, 8], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 11, 12, 9], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 11, 12, 10], [4, 3, 2, 1]]
[[1, 2, 3, 5], [10, 11, 12, 11], [4, 3, 2, 1]]...

그 후 리스트에서 최대값을 구해주면 정답이다.

문자열 슬라이싱을 활용한 더 간단한 코드의 경우처럼 파이썬틱한 코드를 작성할 수 있도록 해야겠다.

소스코드

def solution(land):
    
    def cal(i,j):
        temp=land[i][j]
        for k in range(4):
            if j!=k:
                land[i][j]=max(land[i][j],temp+land[i-1][k])
                #print(land)
    
    N=len(land)
    
    for i in range(1,N):
        for j in range(4):
            cal(i,j)
    
    result=0
    for i in land:
        result=max(result,max(i))
        
    return result

더 간단한 코드

def solution(land):

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

    return max(land[-1])