[프로그래머스_파이썬] 땅따먹기

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

 

풀이

def solution(land):
    answer = 0
    for i in range(1,len(land)):
        for j in range(4):
            land[i][j]+=max(land[i-1][k] for k in range(4) if k!=j)
    answer=max(land[-1])
    return answer

 

설명

4열로 이루어진 N개의 칸을 내려오면서 각 칸에 있는 점수의 합이 최대가 되는 경우를 구해야 하는 문제이다.

단 내려오는 조건은 바로 위에서 밟은 칸의 같은 열의 칸은 밟지 못한다는 것이다.

그렇기 때문에 단순하게 생각하면 각 순간마다 밟을 수 없는 칸을 제외하고 최대값을 더하여 결과를 반환하면 될 것 같지만 여기에는 간단한 트릭이 있어 오답을 내기 쉽다.

왜냐하면 이전에 같은 수들이 있었다면, 밟지 못하는 칸이라는 것은 이전 상황에서 끝나고 새로운 선택을 하는것이 아니라 다음 선택에 영향을 주기 때문이다. 따라서 해당 문제는 동적계획법으로 4개의 시작열로부터 선택들을 쌓아서 모두 가져 간 후 그중 최대값을 반환해야 올바른 결과를 낼 수 있다.