[파이썬] 프로그래머스 : 땅따먹기 (Lv.2)

[파이썬] 프로그래머스 : 땅따먹기 (Lv.2)

 

프로그래머스

 

---

풀이

방향성 생각

딱봐도 DP문제긴 한데 평소같으면 BFS DFS로 풀겠는데 DP 실력이 안늘어서 DP 연습..

출발점 4개에 대해서 전부 DP 돌려서 저장해주면 된다.

점화식이라고 하기엔 이전값 + 이전 인덱스 아닌거 중 최대라서 크게 어렵지는 않다.

def solution(land):

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

    return max(dp[-1])