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

[77] 도둑질

책 구매하기

문제 정보

• 분류: 동적 계획법
• 정답률: 36%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: 원형 DP, 도둑질, 첫 집 포함/제외, 분기
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42897

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

첫 집과 마지막 집을 동시에 털 수 없다는 점 때문에 원형을 선형 두 문제로 나눠야 한다. '첫 집을 포함하는 경우'와 '첫 집을 제외하는 경우'를 각각 풀어 큰 값을 고르면 된다.

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

풀이 흐름

1. 첫 집 포함 케이스에서는 마지막 집을 제외하고 선형 DP를 한다.
2. 첫 집 제외 케이스에서는 두 번째 집부터 끝까지 선형 DP를 한다.
3. 두 결과 중 큰 값을 반환한다.

구현할 때 놓치기 쉬운 부분

집이 원형으로 이어져 있으므로 첫 집과 마지막 집을 동시에 고를 수 없다. 그래서 첫 집을 고른 경우와 고르지 않은 경우를 분리해서 계산해야 한다.

파이썬 정답 코드

def linear(nums):
  if not nums:
    return 0
  if len(nums) == 1:
    return nums[0]

  prev2, prev1 = nums[0], max(nums[0], nums[1])
  for i in range(2, len(nums)):
    prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
  return prev1

def solution(money):
  # 첫 집 포함 케이스에서는 마지막 집을 제외하고 선형 DP를 한다.
  if len(money) == 1:
    # 첫 집 제외 케이스에서는 두 번째 집부터 끝까지 선형 DP를 한다.
    return money[0]
  # 두 결과 중 큰 값을 반환한다.
  return max(linear(money[:-1]), linear(money[1:]))

시간 복잡도

N은 money의 길이이다.

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

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