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

[76] 땅따먹기

책 구매하기

문제 정보

• 분류: 동적 계획법
• 정답률: 57%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: 행 단위 DP, 최대합, 이전 행, 같은 열 금지
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12913

문제를 읽을 때 체크할 포인트

현재 열을 선택했다면 이전 행에서는 같은 열을 고를 수 없다. 그래서 각 칸의 값에 이전 행의 '다른 열 최댓값'을 더해 내려가면 된다.

여기서는 정답 자체보다 '상태를 어떻게 잡을 것인가'가 먼저다. 현재 상태에서 다음 상태로 가는 비용만 잘 세우면, 긴 설명보다 점화식 하나가 더 강하다.

풀이 흐름

1. 첫 행을 초기 상태로 둔다.
2. 각 행 각 열마다 이전 행의 나머지 세 열 중 최댓값을 더한다.
3. 마지막 행의 최댓값을 반환한다.

구현할 때 놓치기 쉬운 부분

같은 열을 연속으로 밟을 수 없다는 조건이 핵심이다. 이전 행의 최댓값을 그대로 더하면 가장 큰 수를 여러 번 같은 열에서 고르는 오류가 생긴다.

파이썬 정답 코드

def solution(land):
  # 첫 행을 초기 상태로 둔다.
  dp = [land[0][:]]

  # 각 행 각 열마다 이전 행의 나머지 세 열 중 최댓값을 더한다.
  for r in range(1, len(land)):
    # 마지막 행의 최댓값을 반환한다.
    prev = dp[-1]
    cur = [0] * 4
    for c in range(4):
      cur[c] = land[r][c] + max(prev[i] for i in range(4) if i != c)
    dp.append(cur)

  return max(dp[-1])

시간 복잡도

N은 land의 행 수이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.