프로그래머스: 땅따먹기

문제

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

 

문제 풀이

 4열로 이루어진 땅이 주어질 때, 한 행에서 1열의 땅을 밟았다면 그다음 행에서는 1열의 땅을 밟을 수 없다는 조건이 있다. 이는 다음과 같이 땅의 값들을 변경시켜 줌으로써 가능하다.

 

 다음 땅에서 획득할 수 있는 점수는 그림과 같이 다음 땅에 선택할 인덱스를 제외한 나머지에서 최대 값을 반환하여 더해주면된다. 이런식으로 값을 중첩해 나아가면 16이라는 최대값을 찾을 수 있다.

코드

def solution(land):
    for i in range(len(land) - 1):
        for j in range(4):
            diff = [num for num in range(4)]
            diff.remove(j)
            land[i + 1][j] += \
                max(land[i][diff[0]], land[i][diff[1]], land[i][diff[2]])

    return max(land[-1])