[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 땅따먹기

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

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

[문제 설명]

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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):
    for n in range(1, len(land)):
        land[n][0] += max(land[n-1][1],land[n-1][2],land[n-1][3])
        land[n][1] += max(land[n-1][0],land[n-1][2],land[n-1][3])
        land[n][2] += max(land[n-1][0],land[n-1][1],land[n-1][3])
        land[n][3] += max(land[n-1][0],land[n-1][1],land[n-1][2])
#         print(land) 
    return max(land[-1])

뻘짓을 하다가 다른 사람의 풀이를 참고했다. 이번엔 동적프로그래밍(DP) 문제라는 것은 알았고, 다만 모든 행들은 다른 행들에 영향을 미칠 가능성이 존재하는데, 이것을 염두해 둔 채로 행을 4개의 열로 유지하는 방법을 캐치하지 못했다. 아무래도 이전 행으로부터 다음 행을 만들어내야 한다는 생각에 빠져있어서 반대로 생각하지 못했던 것 같다. 만들어져야하는 결과 행을 기준으로, 이전 행에서 무엇을 가져와 더할지를 결정하면 간단하게 해결된다.

사실 이전 DP 문제 자체가 만들고자 하는 결과를 이전 것으로부터 연산하여 만들어내는건데.. 이전 DP 문제를 제대로 복습하지 않았다. (ㅠ) 반성합시당

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

열이 4개로 고정되어 있으니 좀 더 간략하게 표현해 볼 수 있다.