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

1. 문제

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

프로그래머스

 

2. 접근방식

• DP문제이다.
• 바텀업 방식으로 해결하면 좋다.
• 점화식 :
  4개의 열(Column) 중 현재 열과 같은 열을 제외한 나머지 값 중 최대값을 현재값에 더한다.

for j in range(4):
	land[i][j] += max([land[i-1][x] for x in list({0, 1, 2, 3} - {j})])

• 가장 큰 합들이 마지막 열에 반영되었기 때문에 가장 아래 열에서 최대값을 선택하면 된다.

 

3. 코드

def solution(land):
    answer = 0

    for i in range(1, len(land)):
        for j in range(4):
            land[i][j] += max([land[i-1][x] for x in list({0, 1, 2, 3} - {j})])
        
    answer = max(land[len(land)-1])
        
    return answer

 

4. 결과