[Python] 프로그래머스 Lv.02 - 땅따먹기

programmers.co.kr/learn/courses/30/lessons/12913#

코딩테스트 연습 - 땅따먹기

[ 알고리즘 ]

DP

 

[문제 접근]

처음엔 매번 최대값을 선택하여 더하는 간단한 문제인줄 알았는데, 그게 아니었다.

다른 분의 풀이를 참고하여 풀이하였다.

전형적인 DP 문제로, 매행의 최대값을 더해준다.

|1|2|3|5|

|5|6|7|8| --> 1행에서 칸이 겹치지 않는 것을 고려한 것 중에 최댓값을 더해준다

|4|3|2|1| --> 위에서 합쳐진 것과 동일시 진행

 

최종적으로 마지막 남은 행의 최대값을 구해주면 끝

 

[코드]

def solution(land):
    answer = 0
    n=len(land)
    
    for i in range(n-1):
        land[i+1][0]+=max(land[i][1],land[i][2],land[i][3])
        land[i+1][1]+=max(land[i][0],land[i][2],land[i][3])
        land[i+1][2]+=max(land[i][1],land[i][0],land[i][3])
        land[i+1][3]+=max(land[i][1],land[i][2],land[i][0])
        
    answer=max(land[n-1])
    

    return answer