[프로그래머스] 땅따먹기

문제

출처

이해

입력

• land
  • 타입: 배열
  • 길이: [1, 10만]
  • 원소
    • 타입: 배열
    • 길이: 4
    • 원소
      • 타입: 정수
      • 범위: [1, 100]
      • 의미: 이 칸을 밟을 때 얻게 되는 점수

출력

• 얻을 수 있는 점수의 최대값

조건

1. 첫 행부터 마지막 행까지 한 행에 한 칸씩 밟고 내려간다.
2. 직전 행에 밟은 열과 동일한 열을 밟을 수 없다.

예시

입출력

입력: 
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	

출력: 
16

접근

문제를 살펴보면 첫 행에서는 4가지 경우, 첫 행을 제외한 나머지 행에서는 3가지 경우가 발생함을 알 수 있다. 매 스텝마다 경우의 수가 3배씩 늘어나고 전체 행이 10만 개이므로 brute-force로는 해결할 수 없음을 알 수 있다. 그런데 조건을 살펴보면 어떤 행에서 발생하는 제약은 그 다음 열을 선택하는 것에만 영향을 미친다는 것을 알 수 있다. 따라서 현재와 1스텝 이전의 과거만 고려하여 문제를 해결할 수 있다.

예를 들어 현재 3행 1열에 있다고 하자. 그럼 2행 1열을 제외한 모든 열에서 현재 상태로 올 수 있다.

2행 2열 -> 3행 1열
2행 2열까지 도착하는 모든 경우 중 최고 점수 + 3행 1열 밟았을 때의 점수

2행 3열 -> 3행 1열
2행 3열까지 도착하는 모든 경우 중 최고 점수 + 3행 1열 밟았을 때의 점수

2행 4열 -> 3행 1열
2행 4열까지 도착하는 모든 경우 중 최고 점수 + 3행 1열 밟았을 때의 점수

이 중 최고 점수가 바로 현재 상태로 올 수 있는 모든 경우 중 가장 높은 점수가 된다. 이를 점화식 형태로 나타내면 다음과 같다.

\[\text {DP}[i][j] = \max_{k\not= j} (\text {DP}[i-1][k]) + \text {land} [i][j]\]

그런데 점화식이면 초기값이 있어야 한다. 즉 1행의 값을 정해야 한다. 이는 쉽게 정할 수 있는데, 1행까지 오면서 얻을 수 있는 가장 높은 점수는 그 칸을 밟았을 때 얻는 점수 뿐이기 때문이다.

구현

"""
dp[i][j]: i행 j열에 위치할 때 가능한 최대 점수
dp의 0행은 land의 0행과 같다.
1행부터 점화식대로 채우면 된다.
"""
def solution(land):
    dp = [[0] * 4 for _ in range(len(land))]
    dp[0] = land[0]
    for i in range(1, len(land)):
        for j in range(4):
            dp[i][j] = max([dp[i-1][k] for k in range(4) if k != j]) + land[i][j]
    return max(dp[-1])