(Python) - 프로그래머스 : 땅따먹기

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

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

 

• 해설 :

N개의 행과 4개의 열로 이루어진 배열이 주어질 때 0번째 행부터 한 행씩 증가하며 4개의 열들 중 하나를 밟는다. 이 때, 직전에 밟았던 열은 밟을 수 없다. N번째 행까지 도달하였을 때 밟고 내려올 수 있는 칸들의 총합 중 가장 큰 값을 찾는 문제이다.

 

 

 

• 풀이 :

DP를 이용하여 해결할 수 있는 문제이다. 각 열마다 선택할 수 있는 최댓값을 갱신해주며 인덱스를 증가시키면 된다.

 

0번째 열일 경우 이전 행,에서 1번 2번 3번의 열을 선택하는 경우들 중 가장 큰 값을 더해주면 되고,

1번째 열일 경우는 이전 행의 0번 2번 3번 열을 선택하는 경우 중 가장 큰 값을 더해주면 된다.

2번과 3번 열은 방식이 동일하므로 생략하겠다.

 

 

 

 

def solution(land):
    for i in range(0, len(land)-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][0],land[i][1],land[i][3])
        land[i+1][3] += max(land[i][0],land[i][1],land[i][2])
    return max(land[-1])