[프로그래머스] Level 2 - 땅따먹기 (Python)

 

 

 

 

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

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

 

 

 

 

✅ Solution

• dp를 이용하여 문제를 해결했다.
• 행을 하나씩 늘려가며 각 열마다 가질 수 있는 최댓값을 할당했다.
  • 예를 들어, 2행 1열까지 오는 최댓값은 1행 2열, 1행 3열, 1행 4열의 최댓값 + 2행 1열의 값이다. 
  • 예를 들어, 2행 2열까지 오는 최댓값은 1행 1열, 1행 3열, 1행 4열의 최댓값 + 2행 2열의 값이다.
• 이를 이용해서 가장 마지막 행까지 구하고 마지막행에서의 최댓값을 리턴해준다.

 

 

 

 

✅ Code

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