[Python] 프로그래머스 Lv2 - 땅따먹기

🔗 문제링크

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

📂 분류

DP

💡 풀이

처음에는 단순하게 행의 최댓값과 열이 겹친다면 두 번째로 큰 수를 구하는 방식으로 접근했다. 하지만 이 접근방식은 잘못된 방식이었고 이 문제는 DP로 접근해야 해결할 수 있는 문제였다.

 

접근방식

• 현재 값에 같은 열은 밟을 수 없으므로 현재 열을 제외한 이전 행의  최댓값을 더해준다.

💻 코드

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

    return max(land[-1])